Na aula desta semana, aprendemos sobre as CFLs e suas propriedades de fechamento. Eu já vi provas de união, interseção e elogio, mas por reversão meu palestrante acabou de dizer que está encerrado. Eu queria ver a prova, então eu tenho procurado nos últimos dias, mas tudo que eu encontrei é que a maioria das pessoas apenas diz que reverter as produções é suficiente para provar isso. Aqueles que são um pouco mais formais afirmam que há uma prova indutiva fácil que você pode dar. Alguém pode me fornecer mais algumas informações / dicas sobre a prova indutiva? Por mais que eu tente, não consigo pensar nisso.
Suas fontes estão certas e receio que haja pouco a acrescentar, exceto o formalismo. I denotar o inverso (espelho) de cadeia por w ^ R .WWWRWR
Se GG é uma gramática, deixe HH ser a sua invertida, de modo para a produção de A → wUMA→W no GG temos A →WRUMA→WR em HH .
Então por indução mostramos que UMA⇒∗GWUMA⇒G∗W sse UMA⇒∗HWRUMA⇒H∗WR .
( Base ) em Zero passos que temos sse .UMA⇒0 0GUMAUMA⇒G0 0UMAUMA⇒0 0HUMAUMA⇒H0 0UMA
( indução ) Assumindo iff , podemos aplicar qualquer produção em (e em no reverso) e obter e respectivamente, onde de fato é o inverso de .UMA⇒∗GW1BW2UMA⇒G∗W1BW2UMA⇒∗HWR2BWR1UMA⇒H∗W2RBW1RB → uB→vocêGGHHUMA⇒∗GW1vocêW2UMA⇒G∗W1vocêW2UMA⇒∗HWR2vocêRWR1UMA⇒H∗W2RvocêRW1RWR2vocêRWR1W2RvocêRW1RW1vocêW2W1vocêW2
Esta é uma prova muito condensada, mas contém todos os ingredientes necessários. Novamente, uma derivação da gramática reversa é o inverso da original. Isso é especialmente claro ao observar as duas árvores de derivação.
isso vale para a linguagem livre do contexto determinístico.
— akashchandrakar
@aksam As CFL determinísticas não são fechadas com reversão. Observe que o determinismo para CFL geralmente é definido com autômatos de empilhamento, não gramáticas.
Há outra maneira de analisar esse problema.
Considere que o idioma é uma CFL. Isso significa que existe uma gramática que satisfaz a CFL. Podemos assumir que isso está na forma normal de Chomsky.eueuG = { N, Σ , P, S}G={N,∑,P,S}
Se faz parte do idioma, trivialmente também faz parte do idioma. Agora, para cada produção do formato , substitua-o por e para as produções do formato , em que , deixa o mesmo.ϵϵϵRϵRP1⟶ A BP1⟶UMABP1⟶ B AP1⟶BUMAP1⟶ aP1⟶umaa ∈ ∑uma∈∑
Na árvore de análise da sequência derivada, é fácil ver que o idioma derivado será exatamente o inverso do idioma inicial, pois a construção reflete a árvore de análise original.
Eu não acho que isso seja "outra maneira": é da mesma maneira que é redigida de uma maneira diferente (e na verdade, eu acho, mais fácil de seguir). A parte em que você diz "é fácil ver" é a parte em que a indução entra. De qualquer forma, +1, pois essa resposta é definitivamente útil.
Primeiramente. As CFLs não são fechadas sob interseção ou complemento (ou diferença para esse assunto). Eles são fechados em União, Concatenação, fechamento em estrela Kleene, substituição, homomorfismo, homomorfismo inverso e reversão. NOTA: Os dois homomorfismos geralmente não são abordados em um curso introdutório de Teoria do Computador.
Para provar a reversão, seja L uma CFL, com gramática G = (V, T, P, S). Seja L R o inverso de L, de modo que a gramática seja G R = (V, T, PR R , S). Ou seja, inverta toda produção.
Ex. P -> AB se tornaria P -> BA
Uma vez que L R é um CFG, portanto, L (L R ) é um CFL.
Bem vindo ao site! Estou surpreso que ninguém tenha notado antes que a pergunta afirma incorretamente que as LFCs estão fechadas sob interseção e complemento.