Odovzdávacie domáce úlohy #3 a #4

Tieto úlohy má každý z vás vyriešiť a riešenie odovzdať v písomnej forme do krabice pred sekretariátom KI (pavilón M, 2. poschodie) DO PONDELKA 14. 10. 2002 8:05. Každá z nich bude hodnotená 3 bodmi. Riešenie každej úlohy píšte na samostatný papier!

Zjednotenie značíme u, prienik ^, doplnok C.

Úloha #3

Daná je bezkontextová gramatika G = (N,T,P,S), kde N={S,A,B,C}, T={a,b}, P={
  S -> ab | C | ABA
  A -> epsilon | SCb | BC
  B -> bb | BCBC | aSA
  C -> epsilon | AC
}
Použitím štandardnej konštrukcie zostrojte bezkontextovú gramatiku G' tak, aby L(G) = L(G') a G' bola bezepsilonová.

Teda G' nesmie obsahovať pravidlá tvaru X -> epsilon (kde X je neterminál) okrem S -> epsilon a nesmie obsahovať pravidlá tvaru X -> uSv (kde X je neterminál, u,v sú z (N u T)*).

Úloha #4

Nech G1 = (N1,T1,P1,S1), G2 = (N2,T2,P2,S2), G3 = (N3,T3,P3,S3) sú dané bezkontextové gramatiky. Zostrojte bezkontextovú gramatiku pre jazyk: L(G1).( L(G2) u L(G3) ). Formálne dokážte správnosť svojej konštrukcie. Vaša konštrukcia by mala byť všeobecná, t.j. fungovať pre ľubovoľné tri bezkontextové gramatiky.