Nepoviny domaci ukol oddevzejte na pristim cviceni na papiru formatu A4. Podepiste jej a napiste na nej svuj e-mail. Doporucuji psat ukol pres kopirak, abyste meli take svoji kopii reseni. To se hodi v okamziku, kdy vam reknu, ze mate ukol dobre - az se budete ucit na zkousku budete tak v ruce mit reseni o kterem mate 100% jistotu, ze je dobre.


1) Prevedte gramatiku na gramatiku bez zbytecnych symbolu:

S -> A | B
A -> aB | bS | b
B -> AB | Ba
C -> AS | b


2) Vytvorte ekvivalentni gramatiku bez e-pravidel:

S -> ABC
A -> BB | e
B -> CC | a
C -> AA | b


3) Odstrante jednoducha pravidla

S'-> S | e
S -> A | B
A -> C | D
B -> D | E
C -> S | a 
D -> S | b 
E -> S | c


4) Ostrante levou rekurzi

A -> Ba | c
B -> CA | bb
C -> Ab | Bb


5) Ostrante levou rekurzi

S -> AB
A -> BS | b
B -> SA | a