Linguagens e gramáticas livres do contexto e autômatos com pilha
Gramáticas livres de contexto
Definimos alguns tipos de gramática. A mais simples foi a gramática regular, estudada em profundidade na anteriormente. Agora, estudaremos um segundo tipo de gramática, as gramáticas livres de contexto. Vimos a definição de gramáticas livres de contexto (GLC), que são aquelas nas quais todas as regras têm exatamente um símbolo não terminal (e nenhum outro símbolo) do lado esquerdo (GARCIA, 2017).
Uma gramática G=(V, T, P, S) é livre de contexto (GLC) se, e somente se, todas as regras são da forma A→w com A∈V e w∈(V∪T)*.
Um exemplo clássico de GLC é a gramática que gera cadeias com os caracteres “(“ e “)” de forma que cada abertura de parênteses corresponde a um fechamento de parênteses posterior.
Considere a linguagem que possui os parênteses corretamente balanceados. L par = {ε,(), (()), ()(), ((())), (())(), ()(()), ()()(), (()()), …}. Esta linguagem é gerada pela gramática a seguir:
- S →ε
- S → SS
- S → (S)
O leitor deve perceber que, pela definição apresentada, toda gramática regular também é uma gramática livre de contexto. Definimos que uma linguagem é regular se, e somente se, existe uma gramática regular que a gere. Da mesma forma, uma linguagem é livre de contexto (LLC) se, e somente se, existe uma gramática livre de contexto que a gere. Portanto, toda linguagem regular L possui uma gramática regular que a gera, gramática estaque também é livre de contexto, portanto, por definição a linguagem L também é livre de contexto.
Entretanto, a recíproca não é verdadeira. Considere a linguagem Lp={ab, aabb, aaabbb, …}. Esta linguagem pode ser facilmente gerada pela seguinte gramática livre de contexto Gp:
- S→aSb|ab
A gramática Gp gera facilmente a cadeia aaabbb , através da derivação:
- S⇒aSb⇒aaSbb⇒aaabbb
PG115