Td 4 automates finis langage l Théorie des langages-tél...

Théorie des langages : Td 4 automates finis langage l

Télécharger PDF

UNIVERSITE Abdelhamid MEHRI Faculté des NTIC Module : TL / Licence 2

ème année

Année 2019/2020

TD n°4

Exercice 1

Donner un automate d’états finis qui reconnait le langage

L= {cc*bd, a(ba)*bcc*ab}. A=(VT, Q q0, δ, F) - VT={a,b,c,d} - q0 : état initial - Q={ q0, q1, q2, q3, q4, q5, q6, q7, q8} - F={ q3}

Exercice 2

Construisez l’automate à états finis qui accepte L dont les mots sur V

T = {a, b, c, d} ne se terminent que par abc. A=(VT, Q q0, δ, F) - VT ={a,b,c,d}

q0 : état initial Q={ q0, q1, q2, q3}

F={ q3} a q

0 q

1 c b q

2 d q

3 q

4 b q

5 b q

6 a c q

7 b b a q

8 q

1 q

2 q

3 a b c q

0 c a,b,c,d Table de transition δ : a b c d q0 {q0, q1} q0 q0 q0 q1 - q2 - - q2 - - q3 - q3 - - - - De l’état q0 sort deux arcs étiquetés avec le symbole a : un arc revient vers l’état q0 et un autre va vers l’état q1. Donc on met dans la case (q0,a) les deux états q0 et q1 (un ensemble {q0,q1}).

Exercice 3

Construisez un automate A sur V

T = {a, b} qui reconnaît un langage dont les mots ne contiennent jamais la sous-chaîne « bab ». - A=(VT, Q q0, δ, F)

- VT={a,b} - q0 : état initial - Q={ q0, q1, q2} - F={ q0, q1, q2} Table de transition δ : a b q0 q0 q1 q1 q2 q1 q2 q0 -

Exercice 4

Construisez un automate A sur V

T = {a, b} qui reconnaît le langage L tel que L = { w {a, b}* / w = an bm a ou w = ba

n ; n, m ≥ 1 } A=(VT, Q q0, δ, F) - VT={a,b} - q0 : état initial - Q={ q0, q1, q2, q3, q4, q5 } - F={ q3,q5} q

0 a b q

1 b q

2 a a q

0