IB102 - úkol 5
Odevzdání: 31.10. 2011
Vypracoval (a): Skupina:
UCO:
Bonus [3 body]
Uvažme abecedu S a slovo u G S*. Definujme slovo u následovně:
.. def
e = e
def
u = o ■ o ■ v, pokud u = a • v, kde a G S a v G S*
Neformálně řečeno, operace ii "zdvojf'každý znak v daném slově. Například pro u = aab platí u = aaaabb.
Podobně definujeme operaci"nad jazyky. Uvažme jazyk L C S*.
r def r .. i r
L = {-u | -u G Lj
Mějme zadaný konečný, deterministický, automat A s totální přechodovou funkcí, který akceptuje jazyk L (A) = L. Najděte algoritmus, který zkonstruuje konečný, deterministický, totálni, automat A, který akceptuje jazyk L (A) = L. Algoritmus naprogramujte. Na výběr máte jazyky Python, C, CH—h, Java, Perl, Pascal a Haskell.
Vstupem pro váš program je textový soubor obsahující několik automatů oddělených od sebe prázdným řádkem. Každý automat je zadán následujícím způsobem. Na prvním řádku je n, počet stavů automatu. Množina stavů automatu je {1,..., n}. Na druhém řádku je m, počet znaků abecedy. Abeceda je dána prvními m znaky anglické abecedy, například pro m = 4 je abeceda {a,b,c,d}. Na třetím řádku je číslo iniciálního stavu. Na čtvrtém jsou čísla koncových stavů oddělená mezerou. Řádky 5 až n + 4 jsou řádky tabulkového zápisu automatu. Každý řádek tudíž obsahuje přesně m čísel z rozmezí 1 až n, která jsou od sebe oddělena mezerou.
Odpovídající automat:
Příklad vstupu:
5 3
1
5 1
2 13
3 2 4
4 3 5
5 4 1 15 2
Výstupní formát je stejný jako vstupní. Odevzdávejte zdrojové kódy vašich programů. Hodnocení bude probíhat na základě výsledků testu. Je možné dostat částečné body za algoritmus i v případě, že kód neprojde testem - ale to jen pokud svůj kód vybavíte komentáři, ze kterých bude jasná myšlenka algoritmu.
V učebních materiálech naleznete také ukázkový vstupní soubor.
	a	b	c
O 1	2	1	3
2	3	2	4
3	4	3	5
4	5	4	1
<r- 5	1	5	2