Intersection de contexte libre avec des langues régulières

On dit que l'intersection d'un langage L sans contexte avec un langage M normal est toujours sans contexte. J'ai compris la preuve de la construction de produits croisés, mais je ne comprends toujours pas pourquoi elle est sans contexte mais pas régulière.

Le langage généré par une telle intersection a des chaînes qui sont acceptées à la fois par un PDA et un DFA. Puisqu'il est accepté par un DFA, ne devrait-il pas être une langue régulière? De plus, si l'intersection est régulière, elle implique également un contexte sans contexte, car toutes les langues régulières sont également sans contexte.

Quelqu'un peut-il m'expliquer pourquoi le langage obtenu par une telle intersection n'est pas régulier?

regular-languages context-free finite-automata formal-grammars sanjeev mk
la source

Considérez. * Comme le langage régulier et son intersection avec un langage sans contexte.

AProgrammer

Ce serait les chaînes du contexte libre. Mais ces chaînes sont également générées par le langage régulier, donc ce serait un langage sans contexte qui est également régulier.

sanjeev mk

La langue pourrait être régulière. Mais ce n'est généralement pas le cas. Pensez à nouveau au contre-exemple donné par AProgrammer. Cela devrait probablement être la réponse. Chaque langue sans contexte est un sous-ensemble d'une langue régulière. Il est vrai que l'intersection des langues CF et REG sera acceptée par DFA de REG, mais il importe également ce qui est rejeté.

Karolis Juodelė

cs.stackexchange.com/q/59886/755

@DW Pertinent mais quelqu'un l'a proposé comme dupe et ce n'est pas ça. Cette question demande pourquoi l'intersection n'est pas toujours régulière; l'autre demande pourquoi l'intersection n'est pas toujours non régulière. La configuration spécifique de cette question (en parlant de chaînes qui sont acceptées à la fois par un DFA et un PDA, donc elles sont acceptées par un DFA, donc la langue est régulière, non?) Signifie que les réponses à l'autre question ne se font pas. t vraiment bien répondre à celui-ci.

David Richerby

Réponses:

Si est sans contexte, il existe un PDA qui l'accepte. Si est régulier, il existe un DFA qui l'accepte. La langue d'intersection se compose des mots qui sont reconnus par et . $L$ $\mathscr{P}$ $M$ $\mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$

Tout mot qui est dans l'intersection est acceptée par , mais pas tous les mots qui sont acceptés par sont à l'intersection: seuls ceux qui sont également acceptées par . $\mathscr{F}$ $\mathscr{F}$ $\mathscr{P}$

La preuve du produit croisé consiste à construire un automate qui contient la mécanique de et , et qui n'accepte que des mots pour lesquels les deux côtés acceptent. L'automate produit croisé est un PDA (et donc le langage reconnu est sans contexte) - intuitivement, parce que le produit croisé avec un DFA à états consiste à prendre copies de et à ajouter flèches entre les états correspondants dans où le DFA a $\mathscr{P} \otimes \mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$ $n$ $n$ $\mathscr{P}$ $(q,a,[q])$ $\mathscr{P}$ $a$ flèches. Le résultat n'est pas un automate fini en général (même pas non-déterministe) car la partie s'appuie sur la pile et cette dépendance ne disparaît pas dans en général. $\mathscr{P}$ $\mathscr{P} \otimes \mathscr{F}$

Un exemple trivial est que est régulier, et si est hors contexte mais pas régulier alors est hors contexte mais pas régulier. $\mathscr{A}^*$ $L$ $L \cap \mathscr{A}^* = L$

Gilles 'SO- arrête d'être méchant'
la source

+1 J'ai presque posté une réponse équivalente à votre dernière phrase. Franchement, le reste de la réponse semble inutile. :)

Patrick87

n'a pas obtenu "l'ajout de flèches (q, a, [q]) entre les états correspondants dans P où le DFA a des flèches". Impossible de visualiser le PDA du produit.

anir