Automaták és formális nyelvek
ZH, 2013. 11. 7.
[Állítsd a tab width-et 4 szóközre]
=============================

1) Adott ez a nyelvtan:
   G = ({S, A, B, C}, {a, b}, S, P)
   
   Ahol P szabályai ezek:
		S -> ASC
		S -> AB
		B -> ACCBB
		B -> A
		C -> bB
		A -> [lambda]
		A -> a
		B -> abB
		B -> bA
		
   A törlő szabályokat szüntesd meg!
   
2) Adva van egy környezetfüggetlen reguláris nyelvet generáló grammatika:
   G = ({S, A, B}, {a, b}, S, P)
   
   Ahol P szabályai ezek:
		S -> aaA
		S -> bbbB
		A -> bS
		A -> aa
		B -> aaS
		B -> [lambda]
		
   a) Konstruálj olyan reguláris grammatikát, ami ugyanazt a nyelvet generálja,
      mint G!
   b) Csinálj véges automatát, ami a G által generált nyelvet fogadja el! Az
      állapotátmeneteket megadhatod gráffal vagy táblázattal.
	  
3) Adott nemdeterminisztikus véges automata:
   M = ({q1, q2, q3, q4}, {a, b}, q1, [delta], {q4})
   
   Ahol [delta] ezzel a táblázattal adott:
	  |   a		|	b
	--|---------|--------
	q1|	q1, q2  |	q1
	q2|	   -	|	q3
	q3|	  q4	|	-
	q4|	  q4	|	q4
	
   a) Csináld meg az állapotátmenet-gráfot, meg egy M-mel megegyező determinisztikus
      automatát!
   b) Add meg magyarul vagy formálisan vagy reguláris kifejezéssel az M által
      elfogadott nyelvet!
	  
4) Legyen L egy {a, b} ábécé feletti nyelv, amelynek szavai b-vel kezdődnek és
   az a-k számát 3-mal osztva 1 a maradék.
   
   a) Csinálj ehhez determinisztikus véges automatát!
   b) Ha már itt tartasz, miért ne csinálnál hozzá egy reguláris kifejezést is?
   
5) Adott ez a determinisztikus véges automata:
   M = ({A, B, C, D, E, F, G, H, I}, {0, 1}, A, [delta], {C, F, I})
   
   [delta]-t ez a táblázat írja le:
   
		0	1
	A	B	E
	B	C	F
	C	D	H
	D	E	H
	E	F	I
	F	G	B
	G	H	B
	H	I	C
	I	A	E
	
   Csinálj minimális állapotszámú (determinisztikus) automatát!
   
6) Adott ez a determinisztikus véges automata:
   M = ({1, 2, 3}, {a, b}, 1, [delta], {3})
   
   Ahol [delta]:
		1	2	3
   a	2	1	3
   b	3	2	1
   
   a) Kell az állapotátmenet gráfja és az M által elfogadott nyelvet leíró
      reguláris kifejezés.
   b) Na meg megcsinálhatod az M által elfogadott grammatikát is.