IB102 úkol 8, příklad 1 Odevzdání: 18. 11. 2019
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. [2 body] Uvažme trasy popsané pomocí úseků stoupání ( ) a klesání ( ); příkladem trasy
může být: . Ke každé trase chceme mít informaci o počtu extrémů na této trase (vrcholů
a údolí; v našem příkladu jsou 2 extrémy). Počet extrémů chceme vyjádřit počtem znaků e
a vytvořit rovnost trasa ≈ odpovídající počet e. Správně utvořené rovnosti budou odpovídat právě
slovům jazyka L.
Formálněji je L jazyk slov nad abecedou Σ = { , , ≈, e} ve tvaru { , }∗ · {≈} · {e}∗ kde
počet podslov a (vrcholů a údolí) na levé straně znaku ≈ odpovídá počtu e (extrémů) na
jeho pravé straně.
Příklady slov patřících do jazyka:
• ≈ e
• ≈
• ≈
• ≈
• ≈ ee
• ≈ ee
Příklady slov nepatřících do jazyka:
• ≈
•
• e
• ≈ e
• ≈ e
• ≈ ≈
Navrhněte bezkontextovou gramatiku, která generuje právě všechna slova jazyka L (tedy správně
vytvořené rovnosti).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.