Linguagens livres de contextos

Introdução

As linguagens livres de contexto constituem a família mais importante de linguagens, a ela pertencendo as linguagens de programação. As linguagens regulares são um caso particular de linguagens livres de contexto, constituindo uma sub-família destas.

Linguagens livres de Contexto

Na teoria de linguagens formais, uma linguagem livre de contexto é uma linguagem gerada por alguma gramática livre de contexto. O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um autômato de pilha. De acordo com a Hierarquia de Chomsky, linguagens livres de contexto são Tipo-2.
Uma linguagem livre de contexto é , a linguagem de todas as cadeias de caracteres não vazias de tamanho par, as primeiras metades sempre preenchidas com "as" e as segundas metades sempre preenchidas com "b"s. L é gerada pela gramática , e é aceita pelo autômato de pilha M = ({q0,q1,qf},{a,b},{a,z},δ,q0,{qf}), em que δ é definido da seguinte forma: δ(q0,a,z) = (q0,a) δ(q0,a,a) = (q0,a) δ(q0,b,a) = (q1,x) δ(q1,b,a) = (q1,x) δ(q1,b,z) = (qf,z) δ(estado1,leitura,desempilha) = (estado2,empilha)
Em que z é a pilha de símbolos inicial e x significa desempilhar.
Gramáticas Livres de Contexto ( tipo 2 ) toda produção P, é da forma A → β onde A ∈ V e β ∈ (V ∪ Σ)* Em contraste com as gramáticas regulares, as gramáticas livres de contexto não têm restrições quanto ao lado direito das produções, apesar do lado esquerdo de cada produção ainda requerer um único não – terminal.
O termo “livre de contexto” reflete o fato que desde que o lado esquerdo de cada produção pode conter somente um não – terminal, a regra de substituição pode ser aplicada sem preocupar-se com o contexto no qual aquele não – terminal é encontrado.
Em Teoria da computação as Gramáticas livres de contexto são também conhecidas como Tipo 2 da Hierarquia de Chomsky, são aquelas em que é levantado o condicionamento das substituições impostas pelas regras