IB102 - úkol 5 Odevzdání: 22.10. 2011 Vypracoval (a): Skupina: UCO: Bonus [5 bodů] Uvažme abecedu E a slovo u G S*. Definujme množinu slov nafoukni(w) následovně: nafoukni(-u) =f {u} nafoukni(-u) =f {a ■ a' \ a' G S} • nafoukni(w) pokud u = a ■ v, kde uGEauG S*. pokud u = e Neformálně řečeno, množina nafoukni(-u) obsahuje slova, která jsou dvakrát delší než slovo u a mají k-tý znak ze slova u vždy na (2k — l)-té pozici. Například pro u = aab platí nafoukni(w) = {aaaaba, aaaabb, aaabba, aaabbb, abaaba, abaabb, ababba, ababbb}. Uvažme jazyk L C S*. Definujeme jazyk L jakožto sjednocení všech množin nafoukni(w), kde u G L. Ĺ d= nafoukni (m) ueL 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. Příklad vstupu: 5 3 1 5 1 2 13 3 2 4 4 3 5 5 4 1 15 2 Odpovídající automat: a b c O 1 2 1 3 2 3 2 4 3 4 3 5 4 5 4 1