dotNETportal.cz

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.