Na Hierarquia de Chomsky, temos as seguintes gramáticas, da mais simples à mais poderosa:
- Gramática regular
- Gramática livre de contexto
- Gramática sensível a contexto
- 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 y
s 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
a
s, depois seguem alguns b
s
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 a
s são do lado esquerdo, e que todos os b
s 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 a
s é maior do que a quantidade de b
s, 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 b
s 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.