IB102 úkol 2, příklad 3 Odevzdání: 3. 10. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplněte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
3. [4 body] (Bonus)
V této úloze máte za úkol naprogramovat algoritmus, který přečte ze vstupu dva konečné automaty
a vrátí konečný automat rozpoznávající sjednocení jazyků rozpoznávaných automaty na vstupu.
Program můžete psát v libovolném z jazyků C, C++, Python, nebo Java, ale musí být možné
ho zkompilovat na počítačích nymfe s Ubuntu, tj. nymfe23–nymfe105, bez použití extra modulů.
Vstupem pro váš program je textový soubor s názvem zadani02.aut, který obsahuje popis dvou
deterministických konečných automatů. Výstupem vašeho programu má být konečný automat rozpoznávající
jazyk, který vznikl jako sjednocení jazyků rozpoznávaných automaty na vstupu. Výstup
program vypisuje na standardní výstup.
Formát vstupu je následující: nejprve je zadán první automat, následuje volný řádek a poté zadání
druhého automatu. Můžete předpokládat, že zadané automaty budou mít totální přechodovou funkci,
budou oba nad stejnou abecedou a že vstupní soubor je validní. Ukázkový vstupní soubor najdete
ve studijních materiálech. Hodnocena bude nejen funkčnost vašeho programu, ale také jeho zdrojový
kód. Za znak konce řádku považujeme znak \n.
Výstupem je jeden automat, zapsaný stejným způsobem jako automaty na vstupu.
Formát automatů
Formát automatů 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.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 2, příklad 3 Odevzdání: 3. 10. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplněte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Příklad vstupu a výstupu
Příklad vstupního souboru:
3
3
1
2
1 2
2 3 3
2 2 2
3 3 3
3
3
1
1
2
3 2 3
2 2 2
3 3 3
Tento vstupní soubor představuje první automat se 3 stavy ({1, 2, 3}), tříprvkovou abecedou ({a, b, c})
a následující přechodovou funkcí:
a b c
↔ 1 2 3 3
← 2 2 2 2
3 3 3 3
Druhý automat má 3 stavy ({1, 2, 3}), tříprvkovou abecedu ({a, b, c}) a následující přechodovou
funkci:
a b c
→ 1 3 2 3
← 2 2 2 2
3 3 3 3
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 2, příklad 3 Odevzdání: 3. 10. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplněte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Výstupem je automat (na standardní výstup), který vznikl sjednocením jazyků rozpoznávaných
automaty ze zadání:
4
3
1
3
1 2 3
2 3 4
2 2 2
3 3 3
4 4 4
Tento výstup představuje automat se 4 stavy ({1, 2, 3, 4}), tříprvkovou abecedou ({a, b, c}) a následující
přechodovou funkcí:
a b c
↔ 1 2 3 4
← 2 2 2 2
← 3 3 3 3
4 4 4 4
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.