Langues sans contexte fermées sous inversion

En classe cette semaine, nous avons découvert les LFC et leurs propriétés de fermeture. J'ai vu des preuves d'union, d'intersection et de compliment, mais pour le renversement, mon conférencier vient de dire que c'était fermé. Je voulais voir la preuve, donc je cherchais depuis quelques jours, mais tout ce que j'ai trouvé, c'est que la plupart des gens disent simplement que renverser les productions suffit pour le prouver. Ceux qui vont un peu plus formellement déclarent simplement qu'il existe une preuve inductive facile que vous pouvez donner. Quelqu'un peut-il me fournir plus d'informations / conseils sur la preuve inductive? Essayez comme je pourrais, je ne peux pas le trouver.

Vos sources ont raison, et je crains qu'il n'y ait que peu de choses à ajouter, à part le formalisme. Je dénote l'inverse (miroir) de la chaîne$w$ par $w^R$.

Si $G$ est une grammaire, laissez $H$ être son inversé, donc pour la production $A\to w$ dans $G$ on a $A\to w^R$ dans $H$.

Ensuite, par induction, nous montrons que $A\Rightarrow_G^*w$ ssi $A\Rightarrow_H^*w^R$.

• ( base ) En zéro étapes, nous avons $A\Rightarrow_G^0 A$ ssi $A\Rightarrow_H^0 A$.
• ( induction ) En supposant $A\Rightarrow_G^*w_1Bw_2$ ssi $A\Rightarrow_H^*w_2^RBw_1^R$ nous pouvons appliquer n'importe quelle production $B\to u$ dans $G$ (et en $H$ à l'envers) et obtenir $A\Rightarrow_G^*w_1uw_2$ et $A\Rightarrow_H^*w_2^Ru^Rw_1^R$ respectivement, où en effet $w_2^Ru^Rw_1^R$ est l'inverse de $w_1uw_2$.

Ceci est une preuve très condensée, mais contient tous les ingrédients nécessaires. Encore une fois, une dérivation de la grammaire inversée est l'inverse de celle d'origine. Cela est particulièrement clair lorsque l'on regarde les deux arbres de dérivation.

Il existe une autre façon de voir ce problème.

Considérez que la langue $L$est une LFC. Cela signifie qu'il y a une grammaire$G=\{N,\sum,P,S\}$qui satisfait la LCF. Nous pouvons supposer que c'est sous la forme normale de Chomsky.

Si $\epsilon$ fait partie de la langue, trivialement $\epsilon^R$fait également partie de la langue. Maintenant pour chaque production du formulaire$P_1 \longrightarrow AB$, remplacez-le par, $P_1 \longrightarrow BA$ et pour les productions du formulaire $P_1 \longrightarrow a$, où $a \in \sum$, laissez la même chose.

À partir de l'arbre d'analyse de la chaîne dérivée, il est facile de voir que le langage dérivé sera exactement l'inverse du langage initial car la construction reflète l'arbre d'analyse d'origine.

Tout d'abord. Les CFL ne sont pas fermées sous intersection ou complément (ou différence d'ailleurs). Ils sont fermés sous Union, Concaténation, fermeture des étoiles de Kleene, substitution, homomorphisme, homomorphisme inverse et inversion. REMARQUE: Les deux homomorphismes ne sont généralement pas couverts dans un cours d'introduction à la théorie des ordinateurs.

Pour prouver l'inversion, Soit L un CFL, avec la grammaire G = (V, T, P, S). Soit L ^R l'inverse de L, telle que la grammaire soit G ^R = (V, T, P ^R , S). Autrement dit, inversez chaque production.

Ex. P -> AB deviendrait P -> BA

Puisque G ^R est un CFG, donc L (G ^R ) est un CFL.