4

Sei que pela hierarquia de Chomsky, toda gramática regular é também uma gramática livre de contexto. Analogamente, sei que uma gramática livre de contexto também é uma gramática sensível ao contexto e etc.

Gostaria de saber como provar que o contrário não se aplica, isto é, que pode ou não existir uma gramática livre de contexto que seja regular. Ou seja, que isso é indecidível.

10
  • 1
    Fiquei um pouco confuso. Você quer provar que nem toda linguagem livre de contexto é regular?
    – Jéf Bueno
    Commented 9/07/2018 às 21:16
  • 1
    Existem casos decidíveis em que a resposta é um tácito não. Você quer um caso indecidível ou um não pra valer? Commented 9/07/2018 às 22:03
  • 1
    @JeffersonQuesado aguardando a resposta :)
    – Maniero
    Commented 9/07/2018 às 22:16
  • 2
    Acima eu quis dizer "que gramática pode ou não ser reduzida". Commented 9/07/2018 às 22:40
  • 1
    @LéoEduardoSilva obrigado pela ênfase, eu havia lido linguagem. Ok, gramática realmente é indecidível. Estou trabalhando na resposta Commented 9/07/2018 às 22:52

1 Resposta 1

5

Na Hierarquia de Chomsky, temos as seguintes gramáticas, da mais simples à mais poderosa:

  1. Gramática regular
  2. Gramática livre de contexto
  3. Gramática sensível a contexto
  4. Gramática irrestrita

Curiosidade: essa não é a nomenclatura de Chomsky. Ele chama de gramática de Markov (ou coisa semelhante) o que os matemáticos e cientistas/teóricos da computação chamam de gramática regular, e também chama de gramática regular o que os matemáticos e cientistas/teóricos da computação chamam de gramática livre de contexto. Não lembro como chama a sensível a contexto, mas a irrestrita mantém a nomenclatura, na minha lembrança.

Uma gramática regular pode ser regular a direita ou regular a esquerda, dependendo de como são suas regras de derivação.

Regular a direita tem os seguintes formatos para regras de derivação (maiúsculas indicam não-terminais, minúsculas indicam terminais; S é o não-terminal inicial):

S ==> 
A ==> aB
A ==> a

Note que a palavra cresce da esquerda para a direita.

Regular a esquerda tem os seguintes formatos para regras de derivação:

S ==>
A ==> Ba
A ==> a

Já gramáticas livres de contexto tem apenas derivações livres de contexto: um não-terminal gerando uma forma léxica qualquer. Uma forma léxica é uma mistura de terminais e não-terminais, em qualquer ordem e qualquer quantidade (até mesmo λ é considerado uma forma léxica). Daí, fica fácil ver que toda produção regular é, também, livre de contexto.

Para alguns jargões da área de linguagens formais, veja essa outra resposta

Uma forma (preguiçosa) de definir uma linguagem como regular é: aquela linguagem que pode ser representada por uma gramática regular. De modo análogo: a linguagem X é aquela que pode ser representada por uma gramática X.

Eu posso dizer que uma linguagem é estritamente livre de contexto se ela não puder ser representada por uma gramática mais simples do que a gramática livre de contexto. E isso vale para todas as outras linguagens.

Tomemos a linguagem L = {a^n b^m |- n inteiro, m inteiro}. Ela é livre de contexto? A resposta é: sim. Prova disso?

S ==>
S ==> A
S ==> B
S ==> AB
A ==> a
A ==> AA
B ==> b
B ==> BB

Agora, ela é estritamente livre de contexto? A resposta é: não.

Estou me valendo do fato de que expressões regulares são equivalentes a gramáticas regulares, pelo menos expressões regulares "puras", no conceito matemático

Prova disso: a*b*.

E a linguagem L = {a^n b^m |- n inteiro, m inteiro, n <= m <= 2n }? Seria ela livre de contexto?

Sim, livre de contexto. E, se quiser o autômato dela, veja aqui.

Agora, seria ela estritamente livre de contexto? Será que eu teria de pesquisar por todas as gramáticas regulares sobre os terminais a e b para analisar isso?

Felizmente, não precisamos fazer uma prova por esgotamento de opções. Elas são infinitamente enumeráveis, mas mesmo assim infinitas, não ia ser possível fazer esse tipo de demonstração em um tempo finito. Então, vamos acochar a matemática e os cintos de segurança?

Logo no começo do texto, eu coloquei como curiosidade que Chomsky chamava esse tipo de gramática como sendo uma gramática de Markov. Sabe por quê? Porque ele, inadvertidamente, usou um processo de Markov para criar um autômato gerador de palavras, ele criou uma máquina de Mealy: para cada transação disparada na cadeia de Markov, um novo símbolo terminal era produzido.

Eu flerto um pouco mais com autômatos generativos e cadeias de Markov nesta resposta.

Então, como um autômato de estados finitos reconhece uma linguagem regular e, também, é uma espécie de cadeia de Markov, temos então que linguagens regulares são intimamente relacionadas com cadeias de Markov.

Se a minha cadeia de Markov permitir laços, e eu esteja em um de seus estados que pertencem ao laço, nada impede que eu faça esse laço infinitas vezes. Afinal, cadeias de Markov só são dependentes do estado atual na hora de determinar o próximo estado.

Para chegar no ponto em que ocorre o laço, talvez eu precise gerar na máquina de Mealy a subpalavra x. O laço completo me geraria a subpalavra y. Daí eu posso finalizar como a subpalavra z. Isso implica que as seguintes concatenações de palavras sejam reconhecidas exatamente pelo mesmo autômato:

xz
xyz
xyyz
xyyyyyyyyyyyyyyz

Ficar repetindo o laço que gera y é chamado de "bombeamento". Posso bombear ys a vontade que a palavra obtida continua pertencente à linguagem. Então, segue o lema do bombeamento para linguagens regulares: se não existir x, y e z que satisfazem essa condição, então a linguagem não é regular.

No caso, nossa gramática é livre de contexto, se ela for não-regular, então não há gramática mais simples que represente essa linguagem, portanto ela seria estritamente livre de contexto.

Tomemos a palavra arbitrária a^n b^m que pertença à linguagem, para algum n e algum m válidos. Posso pegar a subpalavra y de uma das seguintes formas:

  • puro-a: só contenha a
  • puro-b: só contenha b
  • misto: começa com alguns as, depois seguem alguns bs

Qualquer que seja o y misto, bombear o segundo y já torna a nova palavra inválida. Veja: a^n b a b^m; bombeei ab mais uma única vez. Isso não respeitou à definição da linguagem de que todos os as são do lado esquerdo, e que todos os bs são do lado direito.

Para puro-a, o que acontece se eu bombear m vezes a mais? O meu menor resultado seria a^(n+m) b^m. Como a quantidade de as é maior do que a quantidade de bs, essa palavra obtida também não pertence a linguagem.

Então, será que a alternativa puro-b consegue mostrar algo de regular? Bem, a resposta é não. Bombeie 2n vezes, então a menor palavra seria a^n b^(m+2n). A quantidade de bs se tornou estritamente maior do que o dobro da quantidade de a, também desqualificando essa palavra como pertencente à linguagem.

Então, como não há alternativas mais sobrando para provar que é gerada por una cadeia de Markov, então posso afirmar que, por esgotamento, não é gerada por uma cadeia de Markov; isso implica que não há autômato finito que reconheça; e isso implica a inexistência de gramática regular para reconhecer essa linguagem.

Portanto, L = { a^n b^m |- n inteiro, m inteiro, n <= m <= 2n } é estritamente livre de contexto.


Sobre a possibilidade de determinar, genericamente, que uma gramática livre de contexto G, que gera a linguagem L(G), não pode ser simplificado para uma gramática regular R tal que L(G) = L(R)... bem, em alguns casos você consegue decidir entre sim ou não, mas no caso geral isso não é possível.

Você encontrará alguns casos em que não é possível parar com uma resposta para a pergunta. Desconheço a demonstração dessa propriedade, mas conheço muito bem esse resultado da impossibilidade de determinar se uma gramática livre de contexto não é um expressão regular disfarçada.

1
  • Alguém traga um prêmio pra este homem! Jefferson, me ajudou demais! você é o cara e só tenho a agradecer. Commented 10/07/2018 às 16:17

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .