Intersección de contexto libre con lenguajes regulares

Se dice que la intersección de un lenguaje libre de contexto L con un lenguaje regular M siempre está libre de contexto. Entendí la prueba de construcción de productos cruzados, pero todavía no entiendo por qué es libre de contexto pero no regular.

El lenguaje generado por tal intersección tiene cadenas que son aceptadas tanto por un PDA como por un DFA. Dado que es aceptado por un DFA, ¿no debería ser un lenguaje normal? Además, si la intersección es regular, también implica sin contexto, ya que todos los lenguajes regulares también están libres de contexto.

¿Alguien puede explicarme por qué el lenguaje obtenido por tal intersección no es regular?

regular-languages context-free finite-automata formal-grammars sanjeev mk
fuente

Considere. * Como el lenguaje regular y su intersección con un contexto libre.

Programador del

Serían las cadenas del contexto libre. Pero esas cadenas también son generadas por el lenguaje regular, por lo que sería un lenguaje libre de contexto que también es regular.

sanjeev mk

El lenguaje podría ser regular. Pero generalmente no lo es. Piense nuevamente en el contraejemplo dado por AProgrammer. Probablemente debería ser la respuesta. Cada lenguaje libre de contexto es un subconjunto de un lenguaje regular. Es cierto que la intersección de los idiomas CF y REG será aceptada por DFA de REG, pero también importa lo que se rechaza.

Karolis Juodelė

cs.stackexchange.com/q/59886/755

@DW Relevante, pero alguien lo ha propuesto como un tonto y no es eso. Esta pregunta es por qué la intersección no siempre es regular; el otro pregunta por qué la intersección no siempre es no regular. La configuración específica de esta pregunta (hablar de cadenas que son aceptadas por un DFA y un PDA, por lo que son aceptadas por un DFA, por lo que el lenguaje es regular, ¿verdad?) Significa que las respuestas a la otra pregunta no ' Realmente respondo bien a esta.

David Richerby

Respuestas:

Si tiene contexto, entonces hay un PDA que lo acepta. Si es regular, entonces hay un DFA que lo acepta. El lenguaje intersección consiste en las palabras que son reconocidos por y . $L$ $\mathscr{P}$ $M$ $\mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$

Cualquier palabra que se encuentra en la intersección es aceptada por , pero no todas las palabras que son aceptados por se encuentran en la intersección: sólo aquellos que también son aceptados por . $\mathscr{F}$ $\mathscr{F}$ $\mathscr{P}$

La prueba de producto cruzado consiste en construir un autómata que contiene la mecánica de y , y que acepta solo palabras para las cuales ambas partes aceptan. El autómata multiproducto es un PDA (y, por lo tanto, el lenguaje reconocido no tiene contexto), intuitivamente, porque el producto cruzado con un DFA de estado consiste en tomar copias de y agregar flechas entre estados coincidentes en donde el DFA tiene $\mathscr{P} \otimes \mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$ $n$ $n$ $\mathscr{P}$ $(q,a,[q])$ $\mathscr{P}$ $a$ flechas El resultado no es un autómata finito en general (ni siquiera uno no determinista) porque la parte basa en la pila y esta dependencia no desaparece en en general. $\mathscr{P}$ $\mathscr{P} \otimes \mathscr{F}$

Un ejemplo trivial es que es regular, y si tiene contexto pero no es regular, entonces tiene contexto pero no es regular. $\mathscr{A}^*$ $L$ $L \cap \mathscr{A}^* = L$

Gilles 'SO- deja de ser malvado'
fuente

+1 Casi publiqué una respuesta que es equivalente a tu última oración. Francamente, el resto de la respuesta parece innecesaria. :)

Patrick87

no obtuvo "agregar (q, a, [q]) flechas entre estados coincidentes en P donde el DFA tiene flechas". No se puede visualizar cómo será el producto PDA.

anir