IB005 úkol 8, příklad 1 Odevzdání: 17. 4. 2020 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. 1. [0,5 bodu] Informatik v těchto časech koronaviru samozřejmě ve volném čase šije roušky a rozdává je. Zároveň může jít ven, na to však potřebuje mít vždy alespoň jednu roušku, tu pak musí ihned vyprat (čímž získá roušku zpět) nebo ji zahodit do koše (přijde o ni), aby neměl doma kontaminovanou roušku. Informatik tedy může roušku: ušít (u), darovat (d), použít (p), vyprat (v), zahodit (z). Dále musí platit: • S rouškou může provádět cokoli dalšího až potom, co ji ušije. • Může darovat maximálně tolik roušek, kolik jich má již ušitých. • Nemůže darovat použitou, ale nevypranou roušku. • Aby mohl roušku použít na cestu ven, musí mít alespoň jednu ušitou (čistou) roušku. • Ihned poté, co roušku použije, musí ji buď vyprat (tím získá „novou“ čistou roušku), nebo zahodit. • Chce šetřit zdroji, a tak čistou roušku nebude prát ani vyhazovat. • Nemusí darovat všechny roušky - mohou mu nějaké zůstat doma. Mějme tedy jazyk L nad abecedou Σ = {u, d, p, v, z}, který popisuje všechny možné sekvence akcí, které může informatik dělat s rouškami. Slova tohoto jazyka jsou tedy sekvence akcí, které splňují podmínky popsané výše, kde vlevo je ta nejstarší a vpravo ta nejnovější akce. Příklady slov patřících do jazyka L: • ε • uu • uudu • uudpvd • uduududd • uupvpzudd Příklady slov nepatřících do jazyka L: • d • up • duu • uv • udz • upuv Vaším úkolem je sestrojit bezkontextovou gramatiku, která generuje jazyk L. (Gramatika může, ale nemusí obsahovat epsilon pravidla.) Tento úkol je automaticky vyhodnocovaný podobně jako některé úkoly na regulární jazyky. Úkol se odevzdává v ISu přes odpovědník „DÚ odevzdávání: úkol 08, příklad 1,“ v něm však nenajdete žádné další informace k tomuto úkolu, doporučujeme jej tedy otevírat až po vyřešení úkolu. Formát zápisu řešení je obdobný jako u odpovědníků na konstrukci regulárních gramatik, zapisujete však samozřejmě gramatiku bezkontextovou. • Zapisují se pouze pravidla gramatiky, množiny neterminálů a terminálů jsou automaticky odvozeny z těch použitých v pravidlech. Počáteční neterminál je ten, který je uveden jako první. • Názvy neterminálů se zapisují buď jedním velkým písmenem anglické abecedy (např. S, A, Z, . . . ), nebo libovolným řetězcem z malých i velkých písmen anglické abecedy a čísel uzavřeným mezi znaky menší než (<) a větší než (>) (např. , , . . . ). Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi. IB005 úkol 8, příklad 1 Odevzdání: 17. 4. 2020 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. • Jako terminály používejte malá písmena abecedy, právě ta, která jsou abecedou zadaného jazyka. • Prázdné slovo (ε) se zapisuje pomocí řetězce \e (zpětné lomeno, e) nebo unicode znaku malé epsilon (ε). • Přechody se zapisují pomocí šipky složené z pomlčky a větší než (->), jednotlivé alternativy dělíme znakem svislítko (|), např. S -> a | bbb | cS. Všechny přechody náležející jednomu neterminálu musí být na stejném řádku. Příklady správně utvořených gramatik: • S -> aaS | abS | baS | bbS | \e představuje gramatiku G1 = ({S}, {a, b}, {S → aaS | abS | baS | bbS | ε}, S). • S -> aA | bA | ε A -> aS | bS představuje gramatiku G2 = ({A, S}, {a, b}, P2, S), kde P2 = {S → aA | bA | ε, A → aS | bS}. • -> aA | bA | ε A -> a | b představuje gramatiku G3 = ({ init , A}, {a, b}, P3, init ), kde P3 = { init → aA | bA | ε, A → a int | b init }. Všechny výše uvedené gramatiky jsou jazykově ekvivalentní. Příklady špatně utvořených gramatik: • a -> A nepředstavuje gramatiku, protože na místě, kde je nutné uvést neterminál, se nachází malé písmeno, které nemůže být názvem neterminálu. • S -> a S -> b nepředstavuje gramatiku, protože všechna pravidla určená jednomu neterminálu musí být na stejném řádku jako alternativy (a tedy řetězec S -> a | b by již představoval gramatiku). • S -> a | b | nepředstavuje gramatiku, protože znak svislítko (|) je možné používat jen pro oddělení alter- nativ. Případné dotazy k formalismu zápisu prosím směřujte do diskusního fóra. Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.