Automaty + Gramatyki

[akademikos]

Witam. Mam kilka zadan do rozwiazania i potrzebuje pomocy:

1)Zbuduj minimalny deterministyczny automat Rabina-Scotta (bez e(słow pustych) przejsc) rozpoznający jezyk : (11+0)*(00+1)*.

2)Wykaz ze jesli L,S sa bezkontekstowem to L*, L \(\displaystyle{ \cup}\) S rowniez.

3)Zbadaj ktore jezyki sa regularne:
a) A={ \(\displaystyle{ b_{n}}\); n\(\displaystyle{ \in}\)N}, gdzie {\(\displaystyle{ b_{n}}\); n\(\displaystyle{ \in}\) N} jest dowolnym ciagiem arytmetycznym;
b) B={\(\displaystyle{ a^{n} b^{n}}\) ; n\(\displaystyle{ \ge}\)1}.

4)Skonstruuj bk-gramatykę rozpoznającą jezyk z zadania 3b)

5) Skonstruuj garmatyke w postaci normalnej Chomsky'ego dla jezyka z zad 3b)