Théorie des langages TD5

G de type 2 ssi
	A -> α avec α Є (T U N)*

G de type 3 ssi
	A -> a avec a Є T*
	A -> aB avec B Є N
Ou
	A -> a
	A -> Ba

Exercice 1 : Exemples de langages algébriques

Question 1)

L1 = a*b

G = {	T = {a, b}
	N = {mot, A}
	S = mot
	P = {mot -> Ab
		A -> ε | aA}		ou  A -> ε | Aa}	=> type 3 donc pas besoin d’automate à pile
}					Type 2

Question 2)

L2 = anbn	avec n Є N

G = {	T = {a, b}
	N = {mot}
	S = mot
	P = {mot -> ε | a mot b}
	}				Type 2

Automate à pile
      a,λ ; A                                   b,A ; λ

λ,Z ; λ

b,A; λ

 1

 0

 2

On marche ici avec une pile pour faire le compteur :
a,λ,a : Cette syntaxe veut dire : lorsque l’on rencontre « a », on dépile « λ : rien » et on empile « a ». Le  Z correspond au sommet de la pile.
Question 3)

L3 = anbp	avec n > p et n ≠ p où (p, n) Є NxN		 = a+apbp

G = {	T = {a, b}
	N = {mot}
	S = mot
	P = {mot -> AB
B -> ε | aBb
A -> a | aA}
	}				Type 2

Automate à pile
                    				   a,λ ; A                                   b,a ; λ 

b,A ; λ

a,λ ; λ

 2

 1

 0

Question 4)

L4 = anbp	avec n ≠ p où (p, n) Є NxN		 réunion de 2 langages : n>p et n<p

G = {	T = {a, b}
	N = {mot, A ,B, C}
	S = mot
	P = {mot -> AB | BC
B -> ε | aBb
A -> aA
C -> bB}
	}				Type 2