Como mostrar que L = L (G)?

22

Especificar linguagens formais dando gramáticas formais é uma tarefa frequente: precisamos de gramáticas não apenas para descrever as línguas, mas também para analisá-las ou mesmo fazer a ciência apropriada . Em todos os casos, é importante que a gramática em questão esteja correta , ou seja, gere exatamente as palavras desejadas.

Podemos argumentar em alto nível por que a gramática é uma representação adequada do idioma desejado, omitindo uma prova formal. Mas e se estivermos em dúvida ou precisarmos de uma prova formal por algum motivo? Quais são as técnicas que podemos aplicar?

Isso deveria se tornar uma pergunta de referência . Portanto, tenha o cuidado de fornecer respostas gerais, apresentadas didaticamente, ilustradas por pelo menos um exemplo, mas que abranjam muitas situações. Obrigado!

Rafael
fonte

Respostas:

21

As gramáticas são objetos inerentemente recursivos, então a resposta parece óbvia: por indução. Dito isto, os detalhes geralmente são difíceis de acertar. Na sequência, descreverei uma técnica que permite reduzir muitas provas de correção gramatical a etapas mecânicas, desde que algum pré-processamento criativo seja feito.

A idéia básica é não se restringir a palavras de gramática e idioma; é difícil entender a estrutura da gramática dessa maneira. Em vez disso, discutiremos sobre o conjunto de frases que a gramática pode criar. Além disso, dividiremos um objetivo de prova assustador em muitos objetivos pequenos que são mais tratáveis.

Deixe que uma gramática formal com não-terminais , os terminais , regras e a partir símbolo . Denotamos por o conjunto de sentenças que podem ser derivadas de dado , que é . O idioma gerado por é . Suponha que queremos mostrar que para alguns .N T δ S N ϑ ( G ) S δ α ϑ ( G )G=(N,T,δ,S)NTδSNϑ(G)SδL G ( G ) = θ ( L ) T * L = L ( L ) L T *αϑ(G)SαGL(G)=ϑ(G)TL=L(G)LT

O ansatz

Aqui está como vamos fazer isso. Definimos para queM1,,Mk(NT)

  1. ϑ(G)=i=1kMi e
  2. Ti=1kMi=L .

Enquanto 2. é geralmente claro por definição do , 1. requer algum trabalho sério. Os dois itens juntos implicam claramente conforme desejado.L ( G ) = LMiL(G)=L

Para facilitar a notação, vamos denotar .M=i=1kMi

A estrada rochosa

Existem duas etapas principais para realizar essa prova.

  • Como encontrar a (boa) ? Mi
    Uma estratégia é investigar as fases pelas quais a gramática trabalha. Nem toda gramática é receptiva a essa idéia; em geral, este é um passo criativo. Ajuda se pudermos definir a gramática; com alguma experiência, poderemos definir gramáticas mais tratáveis ​​com essa abordagem.

  • Como provar 1.?
    Como em qualquer igualdade definida, existem duas direções.

    • Gϑ(G)M : (estrutural) indução sobre as produções de .G
    • M i SMϑ(G) : Normalmente uma indução por , a partir do um que contém .MiS

Isso é o mais específico possível; os detalhes dependem da gramática e idioma em questão.

Exemplo

Considere o idioma

L={anbncmn,mN}

e a gramática com dada porδG=({S,A},{a,b,c},δ,S)δ

SScAAaAbε

para o qual queremos mostrar que . Quais são as fases pelas quais esta gramática trabalha? Bem, primeiro ele gera depois . Isso informa imediatamente nossa escolha de , a saberc m a n b n M iL=L(G)cmanbnMi

M0={ScmmN},M1={anAbncmm,nN},M2={anbncmm,nN}.

Como e , o item 2. já está . Em direção a 1., dividimos a prova em duas partes, conforme anunciado.M 0T = M 1T = M2=LM0T=M1T=

ϑ(G)M

Realizamos indução estrutural ao longo das regras do .G

IA: Como , ancoramos com sucesso.S=Sc0M0

IH: Suponha por algum conjunto de sentenças que também sabem .X MXϑ(G)XM

IS: Seja arbitrário. Temos de mostrar que qualquer forma tem e tudo o que regra é aplicada seguinte, nós não deixamos . Fazemos isso por distinção completa de casos. Pela hipótese de indução, sabemos que (exatamente) um dos seguintes casos se aplica:α MαXϑ(G)MαM

  • w = S c m m N MwM0 , ou seja, para alguns . Duas regras podem ser aplicadas, ambas derivadas de uma frase em : w=ScmmN
    M
    • ScmScm+1M0 e
    • ScmAcm=a0Ab0cmM1 .
  • w = a n A b n c m m , n NwM1 , ou seja, por alguns : w=anAbncmm,nN
    • wan+1Abn+1cmM1 e
    • wanbncmM2 .
  • w T *wM3 : como , nenhuma outra derivação é possível.wT

Como cobrimos com sucesso todos os casos, a indução está completa.

ϑ(G)M

Realizamos uma prova (simples) por . Observe como encadeamos as provas para que "mais tarde" possa ancorar usando o "anterior" .M i M iMiMiMi

  • mM1 : Realizamos uma indução sobre , ancorando em e usando na etapa.mS S cSc0=SSSc
  • m N A c m S * S cM2 : em um valor arbitrário e induzimos sobre . em , usando a pela prova anterior. A etapa progride via .mnAcm Um um Uma bSScmAcmAaAb
  • m , n N S * um n A b n cM3 : Para arbitrários usamos a prova anterior para .m,nNSanAbncmanbncm

Isso conclui a segunda direção da prova do 1., e terminamos.

Podemos ver que exploramos fortemente que a gramática é linear . Para gramáticas não lineares, precisamos de com mais de um parâmetro variável (na (s) prova (s)), que pode se tornar feia. Se temos controle sobre a gramática, isso nos ensina a mantê-la simples. Considere como exemplo dissuasivo esta gramática que é equivalente a : GMiG

SaAbCεAaAbεCcCε

Exercício

Dê uma gramática para

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

e provar sua correção.

Se você tiver problemas, uma gramática:

Considere com produçõesG=({S,Br,Bl,A,C},{a,b,c},δ,S)

SbSbBlBrBlbBlbABrBrbAbAaAaaCCbcCbcbc

e :Mi

M0={biSbiiN}M1={biBlbooN,io}M2={bkBrbikN,ik}M3={bkaiAa2ibok,o,iN,ko}M4={bkal(bc)iCa2lbok,o,l,iN,ko}M5=L

E as gramáticas não lineares?

O recurso caracterizador da classe de linguagens livres de contexto é a linguagem Dyck : essencialmente, toda linguagem sem contexto pode ser expressa como a interseção de uma linguagem Dyck e de uma linguagem regular. Infelizmente, a linguagem Dyck não é linear, ou seja, não podemos fornecer gramática inerentemente adequada a essa abordagem.

Podemos, é claro, ainda definem e fazer a prova, mas é obrigado a ser mais árdua com induções aninhados e não o que. Há uma maneira geral que conheço que pode ajudar até certo ponto. Alteramos a ansatz para mostrar que geramos pelo menos todas as palavras necessárias e que geramos a quantidade certa de palavras (por comprimento). Formalmente, mostramos queMi

  1. ϑ(G)L e
  2. n N|L(G)Tn|=|LTn|para todos os .nN

Dessa forma, podemos nos restringir à direção "fácil" da ansatz original e explorar a estrutura da linguagem, ignorando os recursos complicados que a gramática pode ter. Obviamente, não há almoço grátis: temos a tarefa totalmente nova de contar as palavras que gera para cada . Para nossa sorte, isso geralmente é tratável; veja aqui e aqui para mais detalhes¹. Você pode encontrar alguns exemplos na minha tese de bacharel .n NG nN

Para gramáticas ambíguas e sem contexto, receio que estamos de volta à ansatz one e thinking caps.


  1. Ao usar esse método específico de contagem, obtemos como bônus que a gramática é inequívoca. Por sua vez, isso também significa que a técnica precisa falhar em gramáticas ambíguas, pois nunca podemos provar 2.
Rafael
fonte