Linguagens Livres de Contexto e Autômatos com Pilha

Linguagem Livre de Contexto (LLC)

A Classe das Linguagens Livres de Contexto (LLC), ou Tipo 2, contém a Classe das Linguagens Regulares, ou seja, compreende um universo mais amplo de linguagens. Com isso:

• Trata-se melhor de questões como parênteses balanceados e construções bloco-estruturadas.
• Os algoritmos reconhecedores e geradores que implementam as Linguagens Livres de Contexto são mais simples e possuem boa eficiência.
• As aplicações e os resultados da LLC são analisadores sintáticos, tradutores de linguagem e processadores de texto em geral.

A forma de estudo dessa classe é desenvolvida por um gerador (gramática) e um operacional ou reconhecedor (autômato), como:

• Gramática Livre de Contexto: Neste caso, as regras de produção são mais livres que na Gramática Regular.
• Autômato com Pilha: Estrutura muito parecida com a do Autômato Finito, adicionando uma memória auxiliar do tipo pilha.

Gramática Livre de Contexto (GLC)

As Linguagens Livres de Contexto são desenvolvidas a partir das Gramáticas Livres de Contexto (GLC). A GLC é um tipo mais complexo de gerador de linguagem, que materializa um completo entendimento do procedimento de construção das palavras pertencentes à linguagem. A GLC é aplicada em compiladores e conversores de documentos.

Definição Formal

Uma Gramática Livre de Contexto (GLC) G é uma quádrupla (V, T, P, S), onde:

• V: Conjunto finito de variáveis ou símbolos não-terminais.
• T: Conjunto de terminais, que é um subconjunto de V.
• P: Conjunto de regras (ou produções), que é um subconjunto finito de (V - T) x V*.
• S: Símbolo inicial (ou variável de início), que é um elemento de V.

Propriedade das Linguagens Regulares

Um fato importante sobre as linguagens regulares é a chamada "propriedade de fechamento". Essa propriedade nos permite construir reconhecedores para linguagens que são construídas a partir de outras linguagens por certas operações. Como um exemplo, a interseção de duas linguagens regulares também é regular. Desse modo, dados autômatos que reconhecem duas linguagens regulares diferentes, podemos construir mecanicamente um autômato que reconhece exatamente a interseção dessas duas linguagens.

Tendo em vista que o autômato para a interseção pode ter mais estados que qualquer um dos dois autômatos dados, essa propriedade de fechamento pode ser uma ferramenta útil para conseguir construir autômatos complexos. Alguns outros fatos importantes sobre linguagens regulares são as chamadas "propriedades de decisão". Nosso estudo dessas propriedades nos dá algoritmos para responder perguntas importantes sobre autômatos. Um exemplo central é um algoritmo para decidir se dois autômatos definem a mesma linguagem.

Autômatos com Pilha

Assim como os Autômatos Finitos estão associados às Linguagens Regulares, os Autômatos com Pilha são os aceitadores ou reconhecedores das Linguagens Livres de Contexto. Isso porque os Autômatos com Pilha possuem, na facilidade do não determinismo, uma importante característica que faz aumentar o poder computacional a fim de reconhecer tais linguagens.

Um Autômato com Pilha ou Autômato com Pilha Não-Determinístico (APND) consiste basicamente de um Autômato Finito Não-Determinístico com uma memória adicional em forma de pilha. Essa pilha independe da fita de entrada, não possui tamanho fixo nem limite máximo. Numa pilha, símbolos novos só podem ser acrescentados no seu topo. Somente o último símbolo armazenado, o que se encontra no topo, pode ser consultado. Os demais símbolos devem esperar que este seja retirado para que possam ser alcançados.

Propriedades das Linguagens Livres do Contexto

As linguagens livres do contexto ocupam uma posição central na hierarquia das linguagens formais. Por um lado, as linguagens livres do contexto incluem importantes, mas restritas, famílias de linguagens, como as linguagens regulares; as linguagens de programação usuais também pertencem a esta classe de linguagens. Por outro lado, existem famílias de linguagens mais amplas das quais as linguagens livres do contexto são casos especiais. Como anteriormente, para as linguagens regulares, veremos as propriedades de fechamento para várias operações, algoritmos para determinar propriedades de membros da família e resultados estruturais, como os lemas do bombeamento.