IB102 úkol 2, příklad 1 Odevzdání: 1. 10. 2018
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] Tento úkol je programovací a odevzdává se pomocí odpovědníku v ISu. Vaším úkolem
je naprogramovat v Pythonu funkci generates(g, w), která pro zadanou regulární gramatiku G
a slovo w rozhodne, zda w ∈ L(G).
Regulární gramatiku v Pythonu popíšeme čtveřici, její první položkou je seznam neterminálů,
druhou položkou seznam terminálů, třetí položkou přechodová funkce (viz dále) a čtvrtou položkou
počáteční neterminál. Přechodová funkce je zadána jako slovník (dict) indexovaný neterminály,
jehož hodnoty jsou seznamy dvojic (terminál, neterminál). Terminály i neterminály budeme zapisovat
jako jednoznakové řetězce a budeme dodržovat konvenci, že terminály jsou malá písmena a
neterminály velká. Neterminál může být případně nahrazen za None pro indikaci, že daná dvojice
představuje terminální pravidlo. Prázdné slovo (ε) zapisujeme jako prázdný řetězec ('').
Například mějme gramatiku G = ({S, A, B}, {a, b}, P, S)
P = {S → ε | a | aA | b | bB
A → a | aA | b | bB
B → b | bB}.
V Pythonu můžeme tuto gramatiku popsat následujícím zápisem.
G = (['S', 'A', 'B'], ['a', 'b'], {
'S': [('', None), ('a', None), ('a', 'A'), ('b', None), ('b', 'B')],
'A': [('a', None), ('a', 'A'), ('b', None), ('b', 'B')],
'B': [('b', None), ('b', 'B')],
}, 'S')
Vaše funkce musí vracet True právě tehdy, když zadané slovo patří do zadané gramatiky, a False
v opačném případě. Můžete se spolehnout, že na vstupu bude validní regulární gramatika:
• bude mít výše popsaný formát,
• všechny seznamy budou bez duplikátů (tedy budou popisovat množiny),
• počáteční neterminál bude v seznamu neterminálů,
• přípustné indexy pro slovník pravidel budou právě všechny neterminály uvedené v seznamu
neterminálů.
Slovo na vstupu bude řetězec (string) složený pouze z terminálů gramatiky. Například:
>>> generates(G, '')
True
>>> generates(G, 'aba')
False
>>> generates(G, 'aab')
True
>>> generates(G, 'abbbbbbbbbb')
True
Úloha je odevzdávána přes odpovědník v ISu. Máte dva pokusy na odevzdání, po obou se vám
případně zobrazí protipříklad na vaše řešení v prohlídce odpovědníku. Vyhodnocovací služba používá
Python 3.7, je tedy pravděpodobné, že v ní bude fungovat cokoli, co funguje v Python 3. Nesmíte
používat žádné dodatečné moduly a žádné IO. Jedinou výjimkou je volitelné použití modulu typing.
Začít můžete tím, že si stáhnete kostru, nebo typovanou kostru pro Python 3.6 a novější (lze
provádět typovou kontrolu pomocí nástroje mypy).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.