Langues CIS 262 - CIS 262 - UPENN

Introduction à la Théorie du calcul

Jean Gallierdépartement des Sciences informatiques et de l’Informationuniversité de Pennsylvanieaphiladelphie, PA 19104, USAe-mail:[email protected]

©c Jean Galliers’il vous plaît, ne produisez pas sans l’autorisation de l’auteur

Mars 5, 2020

4 CONTENU

6.4 Le Lemme De Pompage
6.5 Un Algorithme Rapide pour Vérifier L’Équivalence D’État
7 Grammaires Et Langages Sans Contexte
7.1 Grammaires Sans Contexte
7.2 Dérivations et Langages Sans Contexte
7.3 Formes Normales pour les Grammaires Sans Contexte
7.4 Les Langages Réguliers sont Sans Contexte
7.5 Productions inutiles dans les Grammaires Sans Contexte
7.6 La Forme Normale de Greibach
7.7 Points Les Moins Fixes
7.8 Langages Sans Contexte comme Points Les Moins Fixes
7.9 Points les Moins Fixes et la Forme Normale de Greibach
7.10 Domaines d’Arbres et Arbres de Gorn
7.11 Arbres de Dérivations
7.12 Lemme d’Ogden
7.13 Automates De Poussée
7.14 Des Grammaires Sans Contexte Aux PDA
7.15 Des PDA Aux Grammaires Sans Contexte
7.16 Le Théorème De Chomsky-Schutzenberger
8 Une Étude Des Méthodes D’Analyse LR
8.1 LR(0) – Automates caractéristiques
8.2 Analyseurs de Décalage / Réduction
8.3 Calcul du PREMIER
8.4 L’Intuition Derrière l’Algorithme de Décalage / Réduction
8.5 La Méthode Graphique pour Calculer des Points Fixes
8.6 Calcul de SUIVRE
8.7 AlgorithmTraverse
8.8 Plus onLR(0) – Automates caractéristiques
8.9 LALR(1) – Ensembles de Lookahead
8.10 Calculer D’ABORD, SUIVRE, etc. en présence deRules – Règles
8.11 LR(1) – Automates caractéristiques

Introduction

La théorie du calcul s’intéresse aux algorithmes et aux systèmes algorithmiques: leur conception et leur représentation, leur complétude et leur complexité.

Le but de ces notes est d’introduire certaines des notions de base de la théorie de l’informatique, y compris les concepts des langages formels et de la théorie des automates, la théorie de la calculabilité, quelques bases de la théorie des fonctions récursives et une introduction à la théorie de la complexité. D’autres sujets tels que l’exactitude des programmes ne seront pas traités ici (il n’y a pas assez de temps!).

Les notes sont divisées en trois parties. La première partie est consacrée àlangues formelleset automates. La deuxième partie traite des modèles de calcul, des fonctions récursives et de l’indécidabilité. La troisième partie traite de la complexité de calcul, en particulier les classesPandNP.

5

Bases de la Théorie du Langage Formel

2.1 Examen de Certaines Notations Mathématiques de base et

N, Z, Q, R, C.

Nombres naturels, N = {0, 1, 2,…}.

Les indicateurs, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

Les nationaux,

{

| p, q∈z, q 6 = 0

}

null

Les nombres, R.Les nombres complexes, C = {a + ib/a, b∈R}.

Étant donné n’importe quel setX, l’ensemble de puissance dexis l’ensemble de tous les sous-ensembles deXand est noté 2X. La notation f: X→Y

désigne une fonction avec Domainxandrange(orcodomain) Y.

graph(f) = {(x, f(x)} | x∈X}⊆X× Y

est thegraphoff.

7 8 CHAPITRE 2. BASES DE LA THÉORIE DES LANGAGES FORMELS

Im(f) = f(X) = {y∈ Y |∃x∈ X, y = f(x)}⊆Y

est l’imageoff.

Plus généralement, ifA⊆X, alors

f(A) = {y∈Y|∃x∈A, y = f(x)}⊆Y

est l’image (directe) de A.

IfB⊆Y, alors f-1(B) = {x∈X/f(x)∈B}⊆X

est l’image inverse (ou arrière) de B.

f-1(B) est un ensemble ; il peut être vide même ifB 6 =∅.Étant donné deux fonctionssf: X→Y etg: Y→Z, la fonctiong◦f: X→Zdonné par

(g◦f)(x) = g(f(x)) pour allx∈X

est la compositionoffandg.

La fonction idX: X→X Donnée par

idX(x) = x pour allx∈X

est la fonction d’identité (ofX).

Une fonctionf : X→Y isinjectif (ancienne terminologie un à un) si pour allx 1, x 2 ∈ X,

iff(x 1) = f(x 2), puisx 1 = x 2 ;

de manière équivalente ifx 16 = x 2, puisf(x 1) 6 = f(x 2).

Fait : iFX 6 =∅ (et soY 6 =∅), une fonctionf:X →Y est injective si il existe une fonctionr:Y →X (inverse aléatoire) telle que

r◦ f =idX.

Remarque: ris surjectif.Une functionf: X→Y esturjective (ancienne terminologie) si pour ally∈Y, il y a somex∈ Xsuque thaty = f(X), ifff(X) = Y.

Fait: iFX 6 =∅ (et soY 6 =∅), une functionf:X→Y est surjective iff il y a une fonction: Y→X (aright inverseorsection) telle que

f◦s = idY .

10 CHAPITRE 2. BASES DE LA THÉORIE DU LANGAGE FORMEL

Une relationR⊆X×Xissymétricif pour allx, y∈X, si (x, y)∈R, alors (y, x)∈R

Une relationR⊆X×Xis symétrique iffR−1 ⊆R.

GivenR⊆X×X (une relation onX), defineRnby

R 0 = IXRn + 1 = R◦Rn.

Le Fermeur transnational + ofRis donné par

R+=

⋃

n≥ 1

Rn.

Fait.R+ est la plus petite relation transitive contenantr.

Le Closureur flexible et transitif ∗ ofRis donné par

R∗=

⋃

n≥ 0

Rn = R +IX IX.

Fait.R∗est la plus petite relation transitive et réflexive contenant R.

Une relation R⊆X×X est une relation d’équivalence si elle est réflexive, symétrique et transitive.

Fait. La plus petite relation d’équivalence contenant une relation R⊆X×X est donnée par

(R∪R−1) ∗.

Une relation R⊆X×Xisantisymétricif pour allx, y∈X, si (x, y)∈Rand(y, x)∈ R, alors x = y.

Une relation R⊆X×X Est d’ordre apartiel si elle est réflexive, transitive et antisymétique.

Un ordre partielr ⊆X×X est un ordre total si pour allx, y ∈X, soit (x, y)∈ Ror(y, x)∈ R.

2.2 Alphabets, Chaînes, langues

Notre vision des langues est queun langage est un ensemble de chaînes. À son tour, une chaîne est une finitééquence de lettres d’un alphabet. Ces concepts sont définis rigoureusement comme suit.

Définition 2.1.AnalphabetΣ est n’importe quelfiniteset.

2.2. ALPHABETS, CHAÎNES, LANGUES 11

Nous écrivons souvent Σ = {a 1,…, ak}. Ils sont appelés les symboles de l’alphabet.Exemple:Σ = {a} Σ = {a, b, c} Σ = {0, 1} Σ = {α, β, γ, δ,δ, λ, φ, ψ, ω, μ, ν, ρ, σ, η, ξ, ζ} Une chaîne est une suite finie de symboles. Techniquement, il est pratique de définir des chaînes commefonctions. Pour tout entier≥1, soit

={ 1 , 2 ,…, n},

et forn= 0, soit =∅.

Définition 2.2. Étant donné un alphabet Σ, astringant surσ (ou simplement une chaîne) de longueur nisany fonction

u: → Σ.

L’entier est la longueur du stringu, et il est noté |u|. Lorsque N = 0, la chaîne spéciale : → Σ de longueur 0 est appelée la chaîne vide, ou chaîne nulle, et est notée commeǫ.

Étant donné un stringu : →Σ de longueur n≥1, u(i) est la i-th lettre du stringu. Pour la simplicité de la notation, nous écrivons au lieu de u(i), et nous dénotons la chaîne u = u(1) u(2) ··· u(n) comme

u = u 1 u 2 ··· un,

avec chaque u∈Σ.

Par exemple, si Σ = {a, b} andu: →Σ est défini de telle sorte queu(1) = a, u(2) = b, andu(3) = a, nous écrivonseu = aba.

D’autres exemples de chaînes sont

work, fun, gabuzomeuh

Les chaînes de longueur 1 sont des functionsu: →Σ en choisissant simplement un élémentu(1) = aiin Σ.Ainsi, nous identifierons chaque symbolai∈Σ avec la chaîne correspondante de longueur 1.

L’ensemble de toutes les chaînes sur un alphabet Σ, y compris la chaîne vide, est noté Σ∗.

2.2. ALPHABETS, CHAÎNES, LANGUES 13

Pour la base casen= 0, puisqueeu 0 =ǫ, nous avons

u 0 u =uu = u =uǫ= uu 0.

Pour l’étape d’induction, on a

un +1u = (unu) u par définition deun += (uun) u par l’hypothèse d’induction = u (unu) par associativité = uun +1 par définition deun + 1.

Définition 2.4.Étant donné un alphabet Σ, étant donné deux chaînes quelconques, v∈Σ∗ nous définissons les remarques suivantes comme suit:

u est un préfixe de viff il y a quelque chose ∈Σ∗ tel que

v = uy.

u est un suffixe de viff il y a somex∈Σ∗ tel que

v = xu.

u est une sous-chaîne de viff il y a somex, y∈Σ∗ tel que

v = xuy.

Nous disons queest un préfixe propre (suffixe, sous-chaîne) deviffest un préfixe (suffixe, sous-chaîne) devandu 6 = v.

Par exemple, gais un préfixe degabuzo, zois un suffixe degabuzoandbuzest une sous-chaîne degabuzo.Rappelons qu’un ordre partiel≤ sur un ensemble est une relation binaire≤⊆ S×S qui est réflexive, transitive et antisymétrique.

Les concepts de préfixe, de suffixe et de sous-chaîne définissent les relations binaires sur Σ∗ de manière évidente. On peut montrer que ces relations sont des ordres partiels.

Un autre ordre important sur les chaînes est l’ordre lexicographique (ou dictionnaire).

Définition 2.5. Étant donné un alphabet Σ = {a 1, …, ak} supposé totalement ordonné tel que1 <a 2 <···< ak, étant donné deux chaînes quelconques, v∈Σ∗, nous définissons l’ordre lexicographique comme suit:







(1) ifv = uy, pour certains ∈Σ∗, ou (2) ifu = xaiy, v = xajz, ai < aj, avec iai, aj∈Σ, et pour certains, y, z∈Σ∗.

14 CHAPITRE 2. BASES DE LA THÉORIE DU LANGAGE FORMEL

L’idée est que nous scanuandvsimultanément de gauche à droite, en les comparant au symbole symboluminuto vminv, en commençant parm = 1. S’il n’y a pas de divergence, c’est-à-dire s’ils sont -th symboluminuconvient avec eux -th symbolvminvform = 1,…, /u|, c’est un préfixe dev et nous déclarons que cela correspond à l’ordre lexicographique. Sinon, pendant un certain temps, vous pouvez parcourir un préfixe commun (éventuellement la chaîne vide), puis il y a la plus grande divergence, ce qui signifie que je suis de la forme u = xaiyandvis de la forme v = xajz, avec je 6 = aj (andx, y, z∈Σ∗arbitraire). Ensuite, nous devons rompre l’égalité, etpour ce faire, nous utilisons le fait que les symbolesa 1 < a 2 <···< ak est supposé être (totalement) ordonné, donc nous voyons lequel desaiandaj vient en premier, sayai < aj, et nous déclarons queu = xaiyprecedesv = xajzin l’ordre lexicographique.

Notez que les cas (1) et (2) s’excluent mutuellement. Dans le cas (1),u est un préfixe ofv. Dans le cas (2) v6uandu 6 = v.

Par exemple abb, gallhagergallier.

Il est assez fastidieux de prouver que l’ordre lexicographique est en fait un ordre apartiel.En fait, il s’agit d’un ordre total, ce qui signifie que pour deux chaînes quelconques, v∈Σ∗, soit uv, orvu.

Le long d’une chaîne est défini inductivement comme suit :

RR =ǫ, (ua)R = auR,

où A∈Σ et u∈Σ∗.

Par exemple reillag=gallierR.

Par settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, nous obtenons

aR= (ǫa)R=aǫR=aǫ=a,

namelyaR=afor alla∈Σ.

On peut montrer par induction sur /v/ que

(uv) R = vRuR.

Une astuce utile qui réduit la notation fastidieuse lors de l’induction sur des cordesest l’observation que la corde anonyme w∈Σ∗ de longueur n + 1 (n≥0) peut être écrite comme

w = ua, pour certains u∈Σ∗ et certains symboles∈Σ, avec |u| = n.

16 CHAPITRE 2. BASES DE LA THÉORIE DU LANGAGE FORMEL

IfXis pas l’ensemble vide, puisqueef:X→Nis une injection iff il y a une surjectionr:N→Xs Tel que◦ f = idX, le SETXIS dénombrable iff il y a asurjectionfromNontoX.

Fait. On peut montrer qu’un ensembleest dénombrable s’il est fini ou s’il est en bijection avec N (auquel cas il est infini).

Nous verrons plus tard que N×Nis dénombrable. En conséquence, l’ensemble des nombres rationnels est dénombrable.

Un ensemble n’est pas dénombrable s’il n’est pas dénombrable.

Par exemple, R (l’ensemble des nombres réels) est indénombrable.De même

(0,1) ={ x∈R / 0 < x < 1 }

est incalculable. Cependant, il existe une bijection entre (0,1) etr (trouvez-en un!) L’ensemble 2 de tous les sous-ensembles de n’est pas dénombrable. Ceci est un cas particulier du théorème de cantordiscuté ci-dessous.

Supposons / Σ/= kwith Σ = {a 1, …, ak}. Tout d’abord, observez qu’il existe des chaînes de longueur n et (kn + 1-1) / (k−1) chaînes de longueur au plus Σ; lorsque k = 1, la deuxième formule doit être remplacée par n + 1. En effet, puisqu’une chaîne est une fonction : {1,…, n} → Σ, le nombre de chaînes de longueur est le nombre de fonctions de {1,…, n} à Σ, et comme lecardinalité de Σ isk, il existe de telles fonctions (ceci est immédiatement montré par induction on). Alors le nombre de chaînes de longueur au plus est

1 + k + k 2 +···+ kn.

Si k = 1, ce nombre est n + 1, et si k ≥ 2, comme somme d’une série géométrique, il est (kn + 1-1)/ (k−1).

Si Σ 6 =∅, alors l’ensemble Σ∗ de toutes les chaînes sur Σ est infini et dénombrable, comme nous le montrons maintenant en construisant une bijection explicite à partir de Σ∗onon.

Ifk = 1 writea = a 1, puis

{a} ∗ = {ǫ, a, aa, aaa, …,un,…}.

Nous avons le bijectionn7→anfromNto{a}∗.Ifk≥2, alors on peut penser à la chaîne

u = ai 1 *** ain

comme une représentation de l’entier (u) en basekshifté par (kn−1)/(k−1), avec

2.2. ALPHABETS, CHAÎNES DE CARACTÈRES, LANGUES 17

ν(u) = i 1 kn -1 + i 2 kn− 2 +···+ en – 1 k + en

kn-1 k− 1

( i 1 -1) kn− 1 +···+ (en−1 -1) k + en-1.

( et avec v(ǫ) = 0), où 1≤ij≤kforj = 1, …, n.

Nous le laissons comme un exercice pour montrer quev: Σ∗→Nis une bijection. Trouverexplicitement (c’est-à-dire une formule) pour l’inverse deest étonnamment difficile.

En fait, ν correspond à l’énumération de Σ∗ où upcedesv if|u| <|v|, etduprecedesv dans l’ordre lexicographique if|u|=|v|. Il est facile de vérifier que l’élément ci-dessus (uprecedesv) est un ordre total.

Par exemple, ifk = 2 et si nous écrivons Σ= {a, b}, alors l’énumération commence par

ǫ, 0a, b, 1, 2, aa, ab, ba, bb, 3, 4, 5, 6, aaa, aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

Pour obtenir la ligne suivante, concatenateaon à gauche, puis concatenatebon à gauche. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

Ça marche !

Par contre, si Σ 6 =∅, l’ensemble 2Σ ∗ de tous les sous-ensembles de Σ∗ (toutes les langues) n’est pas dénombrable.En effet, nous pouvons montrer qu’il n’y a pas de surjection de Nonto 2Σ ∗ D’abord, nous montrerons qu’il n’y a pas de surjection de Σ∗ sur 2Σ∗. C’est un cas particulier du théorème de Cantor.Nous prétendons que s’il n’y a pas de surjection de Σ∗ sur 2Σ ∗, alors il n’y a pas non plus de surjection de Nonto 2Σ∗.

Épreuve. Supposons par contradiction qu’il existe une surjectiong : N→ 2 Σ ∗. Mais, si Σ 6 =∅, alorsσ∗ est infini et dénombrable, on a donc la bijectionv : Σ∗→ N. Alors la composition

Σ∗ ν // N

g // 2 Σ ∗

est une surjection, car la bijectionvis une surjection, sig une surjection, et la compositionde surjections est une surjection, contredisant l’hypothèse selon laquelle il n’y a pas de surjection Deσ∗ sur 2Σ ∗.

2.3. OPÉRATIONS SUR LES LANGAGES 19

2.3 Opérations sur les langages

Une façon de construire des langages plus complexes à partir de langages plus simples est de les combiner en utilisant diverses opérations. Tout d’abord, nous passons en revue les opérations de théorie des ensembles de l’union, de l’intersection et de la complémentation.

Étant donné un alphabet Σ, pour deux langues quelconquesl 1, L 2 sur Σ, l’unionl 1 ∪L 2 deL 1 etl 2 est la langue

L 1 ∪L 2 = {w∈Σ∗ | w∈ L 1 ou w∈ L 2}.

L’intersectionl 1 ∩L 2 ofL 1 etl 2 est le langage

L 1 ∩L 2 = {w∈Σ∗ / w∈L 1 et w∈L 2}.

La différence 1-L 2 ofL 1 etl 2 est la langue

L 1-L 2 = {w∈Σ∗/w∈ L 1 et w/∈ L 2}.

La différence est aussi appelée complément elatif.

Un cas particulier de la différence est obtenu lorsque L 1 = Σ∗, auquel cas on définit le complément d’une languelas

L = {w∈Σ∗/w/∈L}.

Les opérations ci-dessus n’utilisent pas la structure des chaînes. Les opérations suivantes utilisentconcaténation.

Définition 2.8.Étant donné un alphabet Σ, pour deux langues quelconquesl1, L2 sur Σ, la concaténationl1 L2 del1 etl2 est la langue

L1 L2 = {w∈Σ∗ /∃u∈ L1,∃v∈ L2, w = uv}.

Pour toute langue, nous définissons comme suit:

L 0 = {}}, Ln + 1 = LnL (n≥0).

En réglantn = 0 inLn + 1 = LnL, Puisque 0 = {}}, on obtient

L 1 = L0 + 1 = L 0 L = {}} L = L,

soL 1 = L.

20 CHAPITRE 2. BASES DE la THÉORIE des langages FORMELS

Les propriétés suivantes sont facile à vérifier:

L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L,(L 1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L 1 (L 2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.

En général, L 1 L 26 = L 2 L 1.So de loin, les opérations que nous avons introduites, à l’exception de la complémentation (sinceL = Σ∗− Lis infini ifLis fini et Σ est non vide), préservent la finitude des langages. Ce n’est pas le cas pour les deux prochaines opérations.

Définition 2.9.Étant donné un alphabet Σ, pour toute langue au-dessus de Σ, Lekleene ∗-closureL∗ ofLis la langue

L∗ =