Interseção de contexto livre com linguagens regulares

Diz-se que a interseção de uma linguagem livre de contexto L com uma linguagem regular M é sempre livre de contexto. Entendi a prova de construção entre produtos, mas ainda não entendo por que ela é livre de contexto, mas não regular.

O idioma gerado por essa interseção possui seqüências de caracteres aceitas por um PDA e um DFA. Como é aceito por um DFA, não deveria ser um idioma comum? Além disso, se a interseção for regular, também implica em contexto livre, pois todos os idiomas regulares também são livres de contexto.

Alguém pode me explicar por que a linguagem obtida por esse cruzamento não é regular?

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

Considere. * Como a linguagem regular e sua interseção com uma linguagem livre de contexto.

AProgrammer

Seriam as cordas do contexto livre. Mas essas strings também são geradas pela linguagem regular, por isso seria uma linguagem livre de contexto que também é regular.

precisa

O idioma pode ser regular. Mas geralmente não é. Pense novamente no contra-exemplo dado pelo AProgrammer. Provavelmente deveria ser a resposta. Toda linguagem livre de contexto é um subconjunto de uma linguagem comum. É verdade que a interseção dos idiomas CF e REG será aceita pelo DFA do REG, mas também importa o que é rejeitado.

usar o seguinte código

cs.stackexchange.com/q/59886/755

@DW Relevante, mas alguém a propôs como burra e não é isso. Esta pergunta está perguntando por que a interseção nem sempre é regular; o outro está perguntando por que o cruzamento nem sempre é não-regular. A configuração específica desta pergunta (falando sobre cadeias de caracteres que são aceitas por um DFA e um PDA, para que sejam aceitas por um DFA, para que o idioma seja regular, certo?) Significa que as respostas para a outra pergunta não são ' Realmente não respondo bem a este.

David Richerby

Respostas:

Se é livre de contexto, existe um PDA que o aceita. Se é regular, existe um DFA que o aceita. O idioma intersecção consiste das palavras que são reconhecidos por e . $L$ $\mathscr{P}$ $M$ $\mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$

Qualquer palavra que está na intersecção é aceito por , mas nem todas as palavras que são aceites pela estão na intersecção: apenas aqueles que também são aceitos por . $\mathscr{F}$ $\mathscr{F}$ $\mathscr{P}$

A prova de produto cruzado consiste em construir um autômato que contém a mecânica de e e que aceita apenas palavras pelas quais ambos os lados aceitam. O autómato de produto cruzado é um PDA (e, por conseguinte, a língua é reconhecido livre de contexto) - intuitivamente, porque o produto cruzado com um DFA -state consiste em tomar cópias $\mathscr{P} \otimes \mathscr{F}$ $\mathscr{P}$ $\mathscr{F}$ $n$ $n$ e adicionar setas entre estados correspondentes em onde o DFA tem $\mathscr{P}$ $(q,a,[q])$ $\mathscr{P}$ $a$ Setas; flechas. O resultado não é um autômato finito em geral (nem mesmo um não-determinístico), porque a parte depende da pilha e essa confiança não desaparece em em geral. $\mathscr{P}$ $\mathscr{P} \otimes \mathscr{F}$

Um exemplo trivial que é é regular, e, se é livre de contexto mas não regular, então é livre de contexto mas não regular. $\mathscr{A}^*$ $L$ $L \cap \mathscr{A}^* = L$

Gilles 'SO- parar de ser mau'
fonte

+1 Eu quase postei uma resposta equivalente à sua última frase. Francamente, o restante da resposta parece desnecessário. :)

Patrick87

não recebeu "adicionando (q, a, [q]) setas entre estados correspondentes em P, onde o DFA possui setas". Não foi possível visualizar como será o PDA do produto.

Anir