Les lemmes suivants sont bien connus.
Lemme 2.1 Si L est un langage algébrique sans e puis il y a la grammaire dans Chomsky
normal
forme qui génère L.
Lemme 2.2 Si L = ∅ et L est régulier alors l est l'union de la langue régulière A1, ..., An
où
chaque Ai est acceptée par un DFA avec exactement un fi état final. Nous démontrons maintenant notre principal théorème.
Théorème 2.3 Si L1 est un langage libre de contexte et L2 est une langue régulière puis L1 ∩L2 est
contexte
libre.
Preuve:
Nous le cas où e ∈/L1 et L2 = ∅. Tous les autres cas, nous laissons au lecteur.
ByLemma2.1wecanassumethereexistsaChomskynormalformgrammarG = (N, Σ, S, P)
pour L1. D'après le lemme 2.2 L2 = A1 ∪ ___ ∪An où chaque Ai où chaque Ai est reconnu par
un DFA
avec exactement un état fi nal.Notez que
L1 ∩L2 = L1 ∩(A1 ∪___∪An) = U(L1 ∩Ai).
i=1
Depuis CFL sont fermées par union (et cela peut être prouvé à l'aide CFG de, donc ce n'est pas un
triche)
nous avons besoin seulement montrer que l'intersection de L1 avec un langue régulière reconnue par un DFA
avec
un fi l'état est CFL. Soit M = (Q, Σ, δ, s, {f}) un DFA avec exactement un état final.
Nous construisons le CFG G0 = (N0, Σ, S0, P0) pour L1 ∩L (M).
Les nonterminals N0 sont triplets [p, V, r] où V ∈ N et p, r ∈ Q.
Pour chaque A → BC de production P, pour chaque p, q, r ∈ Q, nous avons la production
[p, A, r] → [p, B, q] [q, C, r]
à P0.
- Pour chaque production A → σ dans P, pour chaque (p, σ, q) ∈ Q × Σ × Q tel que δ (p, σ) = q nous
ont la production
en P0
- S0 = [s, s, f]
[p, A, q] → σ