Théorie des langages TD3

Exercice 1 : Construire des automates

Question1)  A* : ensemble des mots du langage

On considère l'alphabet A = {0,1} et le langage L = { w A* / le nombre de 1 dans w est pair }.

1

1

I

P

							P : Pair
							I : Impair

           0                                  0

Question 2)

  identifiant
  nombre

3

opEgal

2

identifiant

1

0

			

identifiant nombre

opérateur

T-{identifiant}

4

P

L’état Poubelle n’est pas obligatoire. Même s’il n’est pas représenté, on devine explicitement  qu’il est là.

·  Définition : 
Un état est un état poubelle ssi 
•	Il n'est pas final. 
•	quand on est dans cet état, on ne qu'y rester. 	

Question 3)

Automate déterministe : 	Si pas de transition  dans le puits
				S’il y a une transition, il n’y en a qu’une seule !
 
Automatique indéterministe : Plus d’une transition parte d’un sommet

A

3

2

1

0

		m		 a		   n

A : ensemble des lettres de l’alphabet

Exercice 2 : Déterminisation

Question 1)

m

A-{m}

      m

A-{a,m}

0

   m                     a		   n

3

2

1

m

		

A-{n,m}

A-{m}

Algorithme de déterminisation

m

A-{m}

A-{a,m}

{0,1}

{0,2}

      m

{0,3}

0

   m                     a		   n

m

		

A-{n,m}

A-{m}

Exercice 3 : Equivalence entre automates et langage régulier

Question 1)

G = {	T = {0,1}
N = {A, B}
S = A
P = {A -> 0A | 1B | ε
                   B -> 0B | 1A}
}

A -> a ; a Є T*
A -> aB ; a Є T*, B Є N

ou

A -> a ; a Є T*
A -> Ba ; a Є T*, B Є N

Question 2)