DÉPARTEMENT DE L'INFORMATIQUE ET DU GÉNIE INFORMATIQUE

Plan de leçon – Langages formels et théorie des automates

Année académique
M. Raghavendra Rao Année / Sem: II-II 2017-18
Nb de
Référence Livraison
N° Nom du sujet Livres
Lectures
Méthode
Date
Requis
UNITÉ – I
T1, R4 Craie & 14-12-17
1 Introduction 1
Parler
T1, R4 Craie & 15-12-17
2 Chaînes 1
Parler
Machine à états finis, définition, automate fini T1, R4 Craie & 18-12-17
3 1
modèle Parler
Analyse lexicale et automates finis T1, R4 Craie & 19-12-17
4 1
Acceptation des chaînes et des langues Parler
T1, R4 Craie & 21-12-17
5 automate fini déterministe 1
Parler
T1, R4 Craie & 22-12-17
6 Automate non déterministe 1
Parler
T1, R4 Craie & 23-12-17
7 Diagrammes de transition et reconnaisseurs de langages 1
Parler
Automates finis : NFA avec des transitions e T1, R4 Chalk & 27-12-17
8 2
signification Parler 29-12-17
Acceptation des langages, Équivalence entre NFA T1, R4 Craie & 30-12-17
9 1
avec et sans transitions E Parler
T1, R4 Craie & 2-1-18
10 Conversion de NFA en DFA 1
Parler
T1, R4 Craie & 3-1-18
11 Conversion de NFA en DFA 1
Parler
T1, R4 Craie & 4-1-18
12 minimisation des FSM, équivalence entre deux FSM 1
Parler
Automates finis avec sortie Moore - Mealy T1, R4 Chaux et 6-1-18
13 1
machines Parler
Craie & 7-1-18
Automates finis avec sortie de Melay - Moore T1, R4
14 1 Parler 9-1-18
machines
UNITÉ – II
Langages réguliers : Ensembles réguliers, régulier T1, R4 Craie & 10-1-18
15 1
expressions Parler
T1, R4 Craie & 11-1-18
16 Règles d'identité 1
Parler
Construire des automates finis pour un langage régulier donné T1, R4 Craie & 12-1-18
17 1
expression Parler
18 Conversion des automates finis en régulier T1, R4 1 Craie & 17-1-18
 expression Parler
Conversion des automates finis en régulier T1, R4 Craie & 19-1-17
19 2
expression Parler 20-1-18
Lemme de pompage des ensembles réguliers, propriétés de clôture T1, R4 Craie & 22-1-18
20 des ensembles réguliers 2 Parler 24-1-18
Formalisme grammatical : linéaire à gauche linéaire à droite T1, R4 Craie & 25-1-18
21 1
grammaires Parler
T1, R4 Craie & 27-1-18
22 équivalence entre la grammaire linéaire régulière et l'automate fini 1
Parler
T1, R4 Craie & 30-1-18
23 Inter conversion 2
Parler 1-2-18
grammaire sans contexte T1, R4 Craie & 2-2-18
24 2
formes Parler 3-2-18
T1, R4 Craie & 6-2-18
25 Dérivation la plus à droite et dérivation la plus à gauche de chaînes 2
Parler 12-2-18
UNITÉ – III
Grammaires sans contexte : Ambiguïté dans le contexte T1, R4 Craie & 13-2-18
26 grammaires gratuites 2
Parler 15-2-18
T1, R4 Craie & 16-2-18
27 Minimisation des grammaires hors contexte 1
Parler
T1, R4 Craie & 17-2-18
28 Forme normale de Chomsky 1
Parler
T1, R4 Craie & 19-2-18
29 forme normale de Greibach 1
Parler
lemme de pompage pour les langages contextuels T1, R4 Craie & 20-2-18
30 1
langues Parler
Automates à pile : poussez vers le bas T1, R4 Craie et 21-2-18
31 1
automates Parler
Acceptation par état final et acceptation par vide T1, R4 Craie & 22-2-18
32 1
État et son équivalence Parler
T1, R4 Craie et 23-2-18
33 Équivalence des CFL et PDA 1
Parler
T1, R4 Chalk & 26-2-18
34 Interconversion 1
Parler
T1, R4 Craie & 27-2-18
35 introduction DCFL et DPDA 1
Parler
UNITÉ – IV
T1, R4 Chalk & 28-2-18
36 Machine de Turing 1
Parler
T1, R4 Craie & 1-3-18
37 Machine de Turing 1
Parler
T1, R4 Craie & 2-3-18
38 conception de la machine de Turing 1
Parler
T1, R4 Craie & 5-3-18
39 fonctions calculables 2
Parler
T1, R4 Craie & 6-3-18
40 langages récursivement énumérables 2
Parler
T1, R4 Craie et 7-3-18
41 hypothèse de l'église 2
Parler
 T1, R4 Craie & 9-3-18
42 machine à compter 2
Parler
T1, R4 Craie & 12-3-18
43 types de machines de Turing 2
Parler
T1, R4 Craie & 13-3-18
44 automates linéairement bornés 1
Parler
T1, R4 Craie & 15-3-18
45 CSL 1
Parler

UNITÉ - V
Théorie de la calculabilité : hiérarchie de Chomsky T1, R4 Craie & 16-3-18
46 2
langues Parler
T1, R4 Craie & 19-3-18
47 *Éléments LR(0) et DFA 1
Parler
T1, R4 Craie & 20-3-18
48 Décidabilité des problèmes, 1
Parler
T1, R4 Craie & 22-3-18
49 machines de Turing universelles 1
Parler
T1, R4 Craie & 23-3-18
50 indésirabilité des publications 2
Parler
T1, R4 Craie & 24-3-18
51 problème de correspondance 1
Parler
T1, R4 Chalk & 27-3-18
52 La réduisibilité de Turing, 1
Parler
T1, R4 Craie & 30-3-18
53 définition des problèmes P et NP 2
Parler
T1, R4 Craie & 2-4-18
54 Problèmes NP complets et NP difficiles 1
Parler
T1, R4 Craie & 3-4-18
55 Problèmes NP-complets et NP-difficiles 2
Parler

Questionsimportantes-Parunité:

UNITÉ-I

1. Expliquez l'automate fini et comment les constructions linguistiques peuvent être reconnues ?
2. Listez les automates finis ?
chaîne
4. Décrivez la machine d'état fini avec un diagramme en bloc.
5. Construire un DFA pour accepter le langage de toutes les chaînes ayant un nombre pair de a et un nombre de b.
divisible par trois sur (a+b)*.
6. Expliquer la procédure de conversion d'un AFN en AFD.
7. Qu'est-ce que les automates finis avec sortie et expliquez-les avec des exemples appropriés.
8. Expliquer la procédure pour minimiser l'AFD pour l'expression régulière donnée.
9. a) Construire une machine de Mealy similaire à (bien équivalente sauf pour la sortie initiale de Ms)
machine de Moore suivante.
 0 1
Un B C 0
C
B B 1

C C 0
Un

b) Construisez une machine de Moore similaire à la machine de Mealy suivante.

A B,0 C,1
C,1
B B,1

C C,1
A,1

10. Donnez les machines de Mealy et de Moore pour les processus suivants :
a) Pour une entrée de (0 + 1)*, si l'entrée se termine par 101, afficher A ; si l'entrée se termine par 110, afficher B ;
sinon, sortir C.
b) Pour une entrée de (0 + 1 + 2)*, imprimez le résidu modulo 5 de l'entrée traité comme un ternaire (base 3, avec
chiffres 0, 1 et 2) nombre.

UNITÉ -II

1. Définir l'expression régulière.

2. Écrivez les règles d'identité pour RE
3. Construisez l'AF pour l'Expression Régulière (a/b)*abb.
4. Obtenez le DFA minimisé pour l'RE (a/b)*abb.
5. Expliquer le lemme de pompage pour les ensembles réguliers.
6. Quelles sont les propriétés des ensembles réguliers ?
7. Définir la grammaire et quels sont les types de grammaires ?
E => E + E => E + E * E => id + E * E => id + id * E => id + id * id
pour la phrase id*id+id.
9. Expliquez la grammaire linéaire à droite et la grammaire linéaire à gauche, avec un exemple ?

10. Construire une grammaire régulière G générant l'ensemble régulier représenté par a*b (a+b)*.
11. Si une grammaire régulière G est donnée par S a S/a, trouver une expression régulière pour L (G).

UNITÉ-III

Qu'est-ce qu'une ambiguïté ?

2. Quel problème pose une ambiguïté dans la CFG ?
3. Quelles sont les techniques utilisées pour minimiser le CFG ?
4. Expliquez la CNF et la GNF avec un exemple.
5. Expliquer le Lemma de Pompage pour les grammaires libres de contexte ?
[Link] le concept d'automates à pile ?
7. Écrivez l'automate à pile pour accepter le langage {ww* | w ∈ {0, 1}}
8. Expliquez l'équivalence des langages hors contexte (CFL) et des automates à pile (PDA).

9. Construire un PDA équivalent à la grammaire suivante : S a AA, A a S/bS/a.

Montrez que l'ensemble de toutes les chaînes sur {a, b} comprenant un nombre égal de a et de b est accepté par un
PDA.

UNITÉ - IV

1. Résoudre le problème en utilisant la TM, [anbcn | où n est impair]

2. Expliquez les étapes nécessaires pour concevoir le TM.
3. Expliquez les machines à compteurs avec un exemple approprié.
4. Concevez une machine de Turing pour accepter les chaînes contenant un nombre égal de 0 et de 1.
5. Concevez une machine de Turing pour reconnaître le langage {1n2n3n /n≥1}.
6. Que signifie automates linéairement bornés ?

UNITÉ -V

1. Expliquez la hiérarchie de Chomsky des langues

2. Expliquez le TM universel ?
3. Expliquer les problèmes P et NP ?
4. Expliquer la décidabilité des problèmes. Donnez un exemple.
5. Expliquer le problème de correspondance postale

QUESTIONS D'AFFECTATION
UNITÉ-I
1. a) Étant donné L1={a,ab,a2} et L2={b2,aa} sont les langages sur A={a,b}.
Déterminez i) L1L2 et ii) L2L1.
L* = {ε, b, bbb, bbbb, bbbbb, ...}
c) Soit L = {ab, aa, baa} lesquels des chaînes suivantes sont dans L*
ababababab
2. Déterminez lesquelles des chaînes suivantes sont acceptées par l'automate fini donné.
0011
3. a) Define The following terms: i) DFA and ii)NFA.
b) Concevez un automate fini déterministe (AFD) qui accepte l'ensemble de toutes les chaînes contenant un nombre impair de 0 et impair

Nombre de 1.
4. a) Convertir le NFA suivant en DFA

b) Convertir le NFA suivant avec des transitions ԑ en un NFA sans transitions ԑ .

5. a) Construire l'automate à états minimal pour ce qui suit : État initial : A État final : D

Q/∑ a b
A B A
B Un C
C D B
D D A
E D F
F G E
G F G
H G D
b) Concevoir un automate fini (AF) pour accepter des chaînes contenant 'a' et 'b' de sorte que le nombre de 'b' soit divisible par 3

6. a) Concevoir un DFA pour les langages suivants mostrés ci-dessous : Σ={a,b}

i) L= {w| w ne contient pas la sous-chaîne ab}.

ii) L= {w | w ne contient ni la sous-chaîne ab ni ba}.
iii) L= {w| w est toute chaîne qui ne contient pas exactement deux a’s}.
7. Concevez une machine de Moore et une machine de Mealy pour déterminer le reste modulo 5 pour chaque chaîne ternaire (base 3)

traité comme un entier ternaire.

8. Construisez la machine de Moore pour la machine de Mealy donnée
9. Construire la machine de Mealy pour la machine de Moore suivante

PRÉSENT SUIVANT SORTIE

ÉTAT ÉTAT
i/p=0
q0 q1 q2 q2
q1 trimestre 3q2 q2
q2 q2 q1 q1
q3 q0 trimestreq33

10. Concevez un NFA pour ce qui suit

i) L={ abaan | n≥ 1}
ii) Accepter le langage de toutes les chaînes avec 2 a suivis de 2 b sur {a,b}.
iii) Accepter des chaînes contenant des a et des b de sorte que la chaîne se termine par bb.

UNITÉ-II
1. a) Définir l'expression régulière.
b) Listez les règles d'identité des ensembles réguliers.

c) Prouvez ce qui suit

i) ԑ +1*(011)*(1*(011)*)* = (1+011)*
ii) (1=00*1)+(1+00*1)(0+10*1)*(0+10*1) = 0*1(0+10*1)*
(rs+r)*r=r(sr+r)*
2. a) Expliquer l'équivalence entre NFA et expression régulière.
(OU)
Prouver que chaque langue définie par une expression régulière est également définie par un automate fini.
b) Construire un DFA pour (a+b)*abb.
3. Trouvez l'expression régulière acceptée par le DFA suivant

a)

b)
4. a) Énoncez et prouvez le lemme de pompage pour les langages réguliers. Appliquez le lemme de pompage pour ce qui suit

langue et prouver qu'elle n'est pas régulière L={ambn | pgcd(m,n) = 1}.

b) Montrer que L= {an! |n>=1} n'est pas régulier.
5. a) Obtenez une expression régulière pour accepter des chaînes de a et de b telles que chaque bloc de quatre
des symboles consécutifs contiennent au moins deux a.
b) Donner une expression régulière pour représenter l'ensemble L des chaînes dans lequel chaque 0 est immédiatement

au moins deux 1.
c) Trouvez l'expression régulière pour le langage L={a^{2n}b^{2m}|n≥0, m≥0}.
d) Trouvez l'expression régulière pour L = {w | chaque position impair de w est un 1}
6. a) Définir la Grammaire Régulière. Expliquer en détail l'obtention d'une grammaire linéaire droite et d'une grammaire linéaire gauche pour

le
suivant FA.

b) Trouvez la bonne grammaire linéaire à droite et la grammaire linéaire à gauche pour l'expression régulière

(0+1)*010(1(0+1))*
7. a) Expliquer le processus d'obtention d'un DFA à partir de la grammaire régulière donnée.
b) Construisez un automate fini déterministe (AFD) pour accepter le langage généré par la grammaire contextuelle (CFG) :

i) S 01A, A 10B, B 0A|11. ii). S Aa, A Sb|Ab| ɛ .

8. a) Définir la grammaire hors contexte.

b) i) Qu'est-ce que le CFL généré par la grammaire S abB, A aaBb, B bbAa, A ɛ .

ii) Énoncez en anglais la langue correspondant à la grammaire ci-dessous donnée

S aB|bA, A a|aS|bAA, B b|bS|aBB.
iii) Décrivez la langue générée par la grammaire S aAB, A bBb, B A| ɛ .
c) i) Étant donné la grammaire G comme S 0B|1A, A 0|0S|1AA, B 1|1S|0BB. Trouvez le plus à gauche et le plus à droite

dérivation et arbre de dérivation pour la chaîne 00110101.

ii) Construisez la dérivation la plus à gauche, la dérivation la plus à droite et l'arbre de syntaxe pour la grammaire suivante qui

accepte la chaîne aaabbabbba S aB|bA, A aS|bAA|a, B bS|aBB|b.

9. Écrivez la grammaire libre de contexte pour les langues suivantes
i) L= {anbn|n≥1}
ii) L= {aibjck|i=j}
iii) Langue des chaînes avec un nombre inégal de a et de b.
L= {aibjck| i+j=k,i≥0, j≥0}
v) L= {wwR| w est dans (a,b)* et wR est le renversement de w}
10. a) Écrivez et expliquez toutes les propriétés des ensembles réguliers.

b) Énoncez et prouvez le théorème d'Arden.

UNITÉ-III
1. a) Discutez de l'ambiguïté, de la récursivité gauche et du factoring dans les grammaires contextuelles.

b) Vérifiez si les grammaires suivantes sont ambiguës ou non ?

i) S aAB, A bC|cd, C cd, B c|d.
ii) E E+E|E-E|E*E|E/E|(E)|a.
iii) S aS|aSbS|ԑ .
c) Expliquez le processus d'élimination de l'ambiguïté.
2. a) Expliquer la minimisation ou la simplification des grammaires hors contexte.

b) i) Éliminer les productions nulles dans la grammaire S ABaC, A BC, B b|ɛ , C D|ɛ , D d
ii) Éliminer les productions unitaires dans la grammaire S AB, A a, B C, B b,C D,D E,E a.
iii) Trouvez une grammaire réduite équivalente à la grammaire G dont les productions sont

S AB|CA, B BC|AB, A a, C aB|b.

c) Simplifiez la grammaire suivante : S AaB|aaB, A D, B bbA|ɛ , D E, E F, F aS.
3. a) Expliquer la forme normale de Chomsky.

b) i) Trouvez une grammaire en CNF équivalente à la grammaire S ~S|[S∩S]|p|q.

ii) Trouvez une grammaire en CNF équivalente à G= S bA|aB, A bAA|aS|a, B aBB|bS|b.
4. a) Expliquer la forme normale de Griebach

b) i) Convertissez la grammaire suivante en GNF : E E+T|T, T T*F|F, F (E)|a.

ii) Convertir la grammaire suivante en GNF : S Ba|ab, A aAB|a, B ABb|b.
5. a) Expliquer et prouver le lemma de pompage pour les langages sensibles au contexte.

b) Montrer que les langages suivants ne sont pas des CFL

i) L= {aibj | j=i2} ii) L={anbncj|n≤j≤2n}

c) Considérez la grammaire suivante et déterminez si elle est vide, finie ou infinie
i) S AB, A BC|a, B Cc|B, C a.
ii) S AB, A BC|a, B CC|b, C un, C AB.
6. a) Définir les automates à pile. Expliquer son modèle avec un diagramme clair.
b) Expliquer l'ID de PDA
c) Construire un PDA qui accepte
L= {a3bncn|n≥0}
7. a) Construire une CFG pour le PDA suivant M=({q0,q1},{0,1},{Z0,X},δ,q0,Z0,ф) et δ est
Donné par
δ (q0,1,Z0)=(q0,XZ0), δ (q0,ԑ ,Z0)=(q0, ԑ ), δ (q0,1,X)=(q0,XX)
δ (q1,1,X)=(q1, ԑ ), δ (q0,0,X)=(q1,X), δ (q1,1,Z0)=(q0,Z0).
b) Construire un PDA pour la grammaire S aA, A aABC|bB|a, B b, C c.

8. a) Construire un PDA à deux piles qui accepte L={anbncn|nɛ N}

b) Concevoir un automate à deux piles qui accepte L={anbnanbn | n ɛ N }

9. a) Differentiate Deterministic PDA and Non- Deterministic PDA.

b) Expliquer l'acceptation de PDA par un état vide et un état final.
c) Prouvez l'équivalence de l'acceptation d'un automate à pile par état vide et par état final.

10. a) Expliquez les propriétés de fermeture des langages contextuels libres.

b) Concevoir un PDA non déterministe pour le langage L={0n1n| n≥ 1}.

 UNITÉ-IV
1. a) Définissez la machine de Turing. Expliquez son modèle avec un diagramme clair.

b) Expliquer l'ID d'une machine de Turing.

c) Concevoir une machine de Turing qui accepte les langues suivantes

i) L= {anbncn | n≥0}.
ii) L= {a2nbn | n≥1}.
iii) accepter des chaînes palindromes sur {a, b}.
2. a) Expliquez comment une machine de Turing peut être utilisée pour calculer des fonctions des entiers aux entiers.

b) Concevoir une machine de Turing pour effectuer une soustraction appropriée m - n, qui est définie comme m-n pour

m ≥ n et zéro pour m < n.

c) Concevoir une machine de Turing pour effectuer la multiplication.

3. Concevez une machine de Turing pour calculer ce qui suit

Division de deux entiers

4. Concevez une machine de Turing pour calculer ce qui suit

x²
5. a) Expliquez en détail les différents types de machines de Turing.

b) List the properties of Recursive and Recursively Enumerable Languages.

c) Expliquez ce qui suit
Hypothèse de Church
UNITÉ-V
1. Expliquez la hiérarchie de Chomsky avec un diagramme soigné.

2. Expliquez en détail la machine de Turing universelle.

3. Expliquez ce qui suit
Décidabilité
4. Expliquer les classes P et NP.
Problèmes NP-Complets
b) Expliquez certains problèmes NP-complets en détail.

LIVRESREFERENCÉSPARLECORPSENSEIGNANT:

T1 : Hopcroft H.E. & Ullman J.D., ‘Introductionà la théorie des automates, des langages et
Calcul - Pearson Education.

T2:Thomson,'Introductionàlathéoriedelacomputation',-Sipser2 nd édition
R4 :Lewis H.P. & Papadimition C.H. Pearson, ‘Éléments de théorie de la computation’
-/PHI.
R5 :Mishra et Chandrashekaran, 'Théorie de l'informatique - Automates,

Languesetcomputation,2 nd édition,PHI