Como provar que uma linguagem é livre de contexto?

26

Existem muitas técnicas para provar que uma linguagem não é livre de contexto, mas como posso provar que uma linguagem é livre de contexto?

Que técnicas existem para provar isso? Obviamente, uma maneira é exibir uma gramática sem contexto para o idioma. Existem técnicas sistemáticas para encontrar uma gramática livre de contexto para um determinado idioma?

Para linguagens regulares, não são formas sistemáticas para derivar um autômato regulares gramática / finito de estado: por exemplo, o Myhill-Nerode teorema fornece uma maneira. Existe alguma técnica correspondente para linguagens sem contexto?


Minha motivação aqui é (espero) criar uma pergunta de referência que contenha uma lista de técnicas que geralmente são úteis, ao tentar provar que uma determinada linguagem é livre de contexto. Como temos muitas perguntas aqui que são casos especiais disso, seria bom se pudéssemos documentar a abordagem geral ou as técnicas gerais que se pode usar ao enfrentar esse tipo de problema.

DW
fonte
Permita-me deixar minha observação usual: ao fornecer uma gramática livre de contexto para o idioma em questão, você precisa de uma prova de correção que possa tornar a abordagem bastante difícil.
Raphael
Para tornar essa uma pergunta de referência adequada que podemos colocar nos dumpers com problemas, você poderia adicionar uma resposta sobre a criação de gramáticas e autômatos, talvez com um exemplo cada? Obrigado!
Raphael
Até que o material seja movido para cá, observe que Rick Decker e babou coletaram alguns idiomas típicos sem contexto em uma pergunta duplicada .
Raphael

Respostas:

13

Uma abordagem prática que, em muitos exemplos, funciona [mas nem sempre, eu sei] está tentando encontrar a estrutura de aninhamento das strings na linguagem. "Dependências aninhadas" devem ser geradas ao mesmo tempo em diferentes partes da cadeia.

Também temos a caixa de ferramentas básica :

  1. concatenação: se você puder dividir o idioma em duas partes consecutivas, use esta produçãoSS1S2

  2. união: dividida em partes separadasSS1S2

  3. iteração:SS1Sε

Exemplo 1

Aqui está um exemplo para o aninhamento (obrigado Raphael).

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

Substitua por . Agora podemos reduzir em condições.2 l nn2ln

Substitua por (confuso? é 'oh' e não 'zero'). Aplique ferramentas para união. Trabalhamos com aqui. Também sse e , onde é um novo variável. Substitua por .k > o  ou  k < o o k > o k > o k = s + o s > 0 s k s + okok>o or k<ook>ok>ok=s+os>0sks+o

L1={bs+oal(bc)ma2lbol,m,o,sN,s>0,m2}

Algumas reescritas simples.

L1={bbsboalbcbc(bc)m(aa)lbol,m,o,sN}

Agora vemos a estrutura de aninhamento e começamos a construir uma gramática.

T b U U b U εS1TV , , (consulte: concatenação e iteração aqui)TbUUbUε

O bVbVbW (geramos 'em ambos os lados)o b

WaWaaX

Y b c b c Z b c Z εXYZ , ,YbcbcZbcZε

Exemplo 2

K={akblcml=m+k}

Uma primeira reescrita "óbvia".

K={akbm+kcmm,k0}={akbmbkcmm,k0}

No lingüístico, isso é chamado de "dependência entre séries": a intercalação (geralmente) indica fortemente a ausência de contexto sem contexto. Claro que me somos salvos.m + k = k + mk,m,k,mm+k=k+m

K={akbk+mcmm,k0}={akbkbmcmm,k0}

com produções , ,X a X b ε Y b Y c εSXYXaXbεYbYcε

Da mesma formaK={akblcmm=k+l}={akblclckk,l0}

com produções ,X b X c εSaScXXbXcε


Comentário final: essas técnicas ajudam a criar uma gramática livre de contexto do candidato que, esperamos, reconheça seu idioma. Uma prova de correção ainda pode ser necessária, para garantir que a gramática realmente funcione para reconhecer seu idioma (nada mais e nada menos).

Hendrik Jan
fonte
11

Existe uma caracterização da CFL que pode ser útil, o teorema de Chomsky-Schützenberger .

Linguagem dyck

Deixe um alfabeto. Nós definimos o Dyck -language de pelo contexto-livre gramática com dado porTDT(TT^)TG=({S},TT^,δ,S)δ

SaSa^Sε,aT .

Teorema de Chomsky-Schützenberger

LΣ é livre de contexto se e somente se houver

  • um alfabeto ,T
  • um idioma regular eR(TT^)
  • homomorfismoψ:(TT^)Σ

de modo a

L=ψ(DTR) .

Observe que o homomorfismo é estendido para palavras (símbolo por símbolo) e depois para idiomas (palavra por palavra).

Exemplo

Considere . ComL={anbncmn,mN

  • T={[,} (e, canonicamente, ),T^={],}
  • R=L([]) e
  • ψ(x)={a,x=[b,x= ]ε,x=c,x= 

o teorema implica que é livre de contexto, em particular porqueL

DTR={[n]nmmn,mN}

Exemplo 2

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

abcbbko

  • T={[,,,<}
  • R=L(<+>+[++])L([++]<+>+)
  • ψ(x)={b,x{,,<}a,x=[aa,x= ]bc,x=ε,else

L=ψ(DTR)[]wDTR

DTR={<p>po[lmm]lop1,o0,l0,m2} {}

e com isso

ψ(DTR)={bp+oal(bc)ma2lbop1,o0,l0,m2} {}={bkal(bc)manbok,l,m,n,oN,k>o,2l=n,m2} {}=L.

Para gramáticas e autômatos

Se queremos ter um autômato ou gramática no final, temos mais trabalho pela frente.

  • DTRψ

  • RDTψ

TRψ

Rafael
fonte
É indecidível se um determinado idioma é livre de contexto.
Reinierpost