IB102 – úkol 2, příklad 3 Odevzdání: 12. 10. 2015
Vypracoval(a): UČO:
Skupina:
3. [4 body] (Bonus)
V této úloze máte za úkol naprogramovat simulátor konečného automatu. Váš program
přečte ze vstupu konečný automat a pro zadaná slova rozhodne, jestli patří do jazyka
akceptovaného tímto automatem.
Program můžete psát v libovolném z jazyků C, C++, Python, Java nebo Haskell, ale
musí být možné ho zkompilovat na počítačích nymfe s Ubuntu 14.04, například nymfe100
bez použití extra modulů.
Vstupem pro váš program je textový soubor s názvem zadani02.aut, který obsahuje
popis deterministického konečného automatu a poté seznam slov, o nichž se má rozhodnout,
jestli je zadaný automat akceptuje. Výstupem vašeho programu má být pro každé
zadané slovo rozhodnutí, zdali ho zadaný automat akceptoval, nebo ne. Výstup program
vypisuje na standardní výstup.
Formát vstupu je následující: nejprve je zadání automatu, následuje volný řádek a
poté na každém dalším řádku až do konce souboru jedno slovo, přičemž prázdný řádek
znamená slovo ε. Můžete předpokládat, že zadaný automat bude mít totální přechodovou
funkci a každé ze zadaných slov bude nad abecedou daného automatu. Ukázkový vstupní
soubor najdete ve studijních materiálech.
Za znak konce řádku považujeme znak \n.
Formát automatu
Formát automatu je následující (po řádcích):
1. n, počet stavů automatu (stavy jsou číslovány sekvenčně od 1),
2. počet písmen abecedy (malá písmena bereme postupně ze začátku anglické abecedy,
písmen nebude více než 26),
3. číslo iniciálního stavu (od 1 do n),
4. počet akceptujících stavů (od 1 do n),
5. mezerou oddělená čísla akceptujících stavů (každé od 1 do n),
6. na dalších řádcích (6 až n + 5) následuje tabulka přechodové funkce.
IB102 – úkol 2, příklad 3 Odevzdání: 12. 10. 2015
Vypracoval(a): UČO:
Skupina:
Příklad vstupu a výstupu
Příklad vstupního souboru:
5
3
1
2
5 1
2 1 3
3 2 4
4 3 5
5 4 1
1 5 2
aaaa
ababac
ac
aba
Tento vstupní soubor představuje automat s 5 stavy ({1, 2, 3, 4, 5}), 3prvkovou abecedou
({a, b, c}) a následující přechodovou funkcí:
a b c
↔ 1 2 1 3
2 3 2 4
3 4 3 5
4 5 4 1
← 5 1 5 2
Slova, o jejichž akceptování se má rozhodnout, pak jsou {aaaa, ababac, ac, ε, aba}.
Výstupem je na standardní výstup po řádcích pro každé slovo buď 1, pokud ho zadaný
automat akceptuje, nebo 0, pokud ho zamítá. Tedy:
1
1
0
1
0