Interseção de contexto livre com linguagens regulares

16

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?

sanjeev mk
fonte
12
Considere. * Como a linguagem regular e sua interseção com uma linguagem livre de contexto.
AProgrammer
11
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
8
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
11
@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:

20

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

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

A prova de produto cruzado consiste em construir um autômato que contém a mecânica de P e F 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 n DFA -state consiste em tomar n cópiasPFPFnn e adicionar ( Q , um , [ q ] ) setas entre estados correspondentes em P, onde o DFA tem umP(q,a,[q])PaSetas; 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 PF em geral.PPF

Um exemplo trivial que é é regular, e, se L é livre de contexto mas não regular, então G Um * = L é livre de contexto mas não regular.ALLA=L

Gilles 'SO- parar de ser mau'
fonte
2
+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