Programátorská hádanka aneb k čemu jsou konečné automaty

Tomáš Herceg       10. 4. 2009       C#, Offtopic       7485 zobrazení

Tento semestr máme ve škole předmět Automaty a gramatiky, který jsem až do dneška neměl tak moc rád, protože jsem sice chápal, k čemu je to dobré, nicméně nikdy jsem nikdy nenarazil ve své praxi na úlohu, kde by se nabyté poznatky hodily. Až dnes.

Co to vlastně konečný automat je? Konečný automat je taková pěkná věc, která je tvořena množinou stavů (z nichž právě jeden je počáteční a několik jich může být koncových, a to i ten počáteční), abecedou (tedy množinou znaků, se kterou automat pracuje) a přechodovou funkcí (která říká, do kterého stavu se dostanu, když jsem v nějakém konkrétním stavu a přečtu ze vstupu dané písmeno z abecedy). Automat začíná v počátečním stavu, postupně čte po znacích vstupní řetězec a přechází mezi stavy. Jakmile vstup skončí, odpovědí automatu je ANO či NE, podle toho, jestli je nebo není v koncovém stavu.

Zásadní otázka: K čemu to je? Dnes jsem narazil na úlohu, ke které se konečné automaty docela pěkně hodí a bez nich by se to psalo dost těžko (asi bych musel použít regexpy, ale i tak bych musel řetězec dále procházet a hledat v něm jisté věci). Použitím automatu se to poměrně zjednoduší, pokud k tomu samozřejmě člověk napíše komentář, jak to funguje a o co jde, aby to také ještě někdy pochopil.

Schválně, jestli poznáte, k čemu tento automat používám? Aktuální stav je v proměnné state, přechodová funkce je definována tím šíleným switchem (stavů je 7), c je právě načtený znak koncové stavy jsou 0 a 1.

        private int Method(string line)
        {
            int ind = 0;
            int state = 0;
            for (int i = 0; i < line.Length; i++)
            {
                // načíst znak a přejít do nového stavu
                char c = line[i];
                switch (state)
                {
                    case 0:
                        if (c == '@') state = 1;
                        else if (c == '"') state = 3;
                        else if (c == '\'') state = 5;
                        break;

                    case 1:
                        if (c == '"') state = 2;
                        else state = 0;
                        break;

                    case 2:
                        if (c == '"') state = 1;
                        break;

                    case 3:
                        if (c == '\\') state = 4;
                        else if (c == '"') state = 0;
                        break;

                    case 4:
                        state = 3;
                        break;

                    case 5:
                        if (c == '\\') state = 6;
                        else if (c == '\'') state = 0;
                        break;

                    case 6:
                        state = 5;
                        break;
                }

                // TODO: hádejte, co se tady děje a k čemu slouží automat?
                if ((state == 0) || (state == 1))
                {
                    if (c == '{') ind++;
                    if (c == '}') ind--;
                }
            }
            return ind;
        }

Poznámka pro rýpavé – vím, že to není obyčejný konečný automat, je to Mealyho stroj, protože kromě toho, že přechází mezi stavy, také dělá ještě něco jiného, má jistou výstupní funkci. Ale to není pro tuto hádanku podstatné.

Pokud máte nějaký tip, co by to tak asi mohlo být, napište do diskuse.

 

hodnocení článku

0       Hodnotit mohou jen registrované uživatelé.

 

Nový příspěvek

 

...

Vypada to jako validacni metoda c# souboru ktera vraci 0 je li struktura ok.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Programátorská hádanka aneb k čemu jsou konečné automaty

Neznám C# a neumím dát konkrétní tip na použití funkce, ale odhaduji, že indikuje nevypárované složené závorky, ignoruje ty uzavřené mezi uvozovky nebo apostrofy...

nahlásit spamnahlásit spam 0 odpovědětodpovědět

Diskuse: Programátorská hádanka aneb k čemu jsou konečné automaty

Třeba na tohle:

public bool CheckFile(string fileName)
{
	return System.IO.File.ReadAllLines(fileName).Sum(line => Method(line)) == 0;
}
nahlásit spamnahlásit spam 1 / 1 odpovědětodpovědět

Tak tohle použití mě nenapadlo, používám to na trochu něco jiného, ale i tohle by šlo.

nahlásit spamnahlásit spam 0 odpovědětodpovědět

To chápu, jen jsem to nechtěl provařit :-).

nahlásit spamnahlásit spam 0 odpovědětodpovědět
                       
Nadpis:
Antispam: Komu se občas házejí perly?
Příspěvek bude publikován pod identitou   anonym.

Nyní zakládáte pod článkem nové diskusní vlákno.
Pokud chcete reagovat na jiný příspěvek, klikněte na tlačítko "Odpovědět" u některého diskusního příspěvku.

Nyní odpovídáte na příspěvek pod článkem. Nebo chcete raději založit nové vlákno?

 

  • Administrátoři si vyhrazují právo komentáře upravovat či mazat bez udání důvodu.
    Mazány budou zejména komentáře obsahující vulgarity nebo porušující pravidla publikování.
  • Pokud nejste zaregistrováni, Vaše IP adresa bude zveřejněna. Pokud s tímto nesouhlasíte, příspěvek neodesílejte.

přihlásit pomocí externího účtu

přihlásit pomocí jména a hesla

Uživatel:  
Heslo:  

zapomenuté heslo

 

založit nový uživatelský účet

zaregistrujte se

 
zavřít

Nahlásit spam

Opravdu chcete tento příspěvek nahlásit pro porušování pravidel fóra?

Nahlásit Zrušit

Chyba

zavřít

feedback