IB005 úkol 12, příklad 2 Odevzdání: 16. 5. 2022 12:00
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [0,5 bodu] Mějme zadanou abecedu Σ = {a, b, c} a jazyk L = {w#p | w ∈ Σ∗, p je permutace w}.
Příklady slov, která patří do jazyka L: #, aa#aa, abc#abc, abc#cab, abcccaaba#cacacbaba.
Příklady slov, která nepatří do jazyka L: ε, abab, abcac#acac, aaa#aaaa, bbb#b, abcac#cabab.
Úlohu můžete řešit jedním z následujících formalismů. Nekonstruujte LBA a zároveň gramatiku,
stačí si vybrat jeden ze způsobů a úlohu řešit pomocí něj.
• Sestrojte deterministický lineárně ohraničený automat (LBA) akceptující jazyk L.
Nejdříve slovně popište fungování LBA včetně popisu funkcionality jednotlivých stavů, poté
ho zadefinujte i formálně. Váš LBA může mít nanejvýš 18 stavů (včetně stavů accept a reject).
• Sestrojte kontextovou gramatiku (CSG) generujíci jazyk L.
Nejdříve slovně popište hlavní myšlenku fungování vaší gramatiky, včetně popisu funkcionality
jednotlivých pravidel, poté ji zadefinujte i formálně. Vaše gramatika může mít nanejvýš 20
pravidel.
Poznámka: Pokud píšete řešení v TEXu a nevejde se vám, před odevzdáním prosím odmažte zadání.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.