Linguagens Livres de Contexto Resumo

Prévia do material em texto

Linguagens Livres-de-Contexto & 
Autômatos com Pilha 
Gramáticas Livres de Contexto 
Método mais poderoso de descrever linguagens, pois 
podem descrever características recursivas. 
Aplicação: especificação e compilação de linguagens de 
programação. 
Gramática: coleção de regras de substituição. 
●Cada linha é uma regra e tem um símbolo e uma cadeia, 
separados por uma seta. 
●Símbolo é uma variável; 
●A cadeia consiste de variáveis e outros símbolos 
chamados terminais. 
●Os terminais pertencem ao alfabeto; 
●Uma variável é a variável inicial; 
 
Variáveis: A e B 
Variável inicial: A 
Terminais: 0, 1 e # 
Gramatica é usada para descrever uma linguagem 
gerando cada cadeia daquela linguagem da seguinte 
maneira: 
1. Escreva a variável inicial. Ela é a variável no lado 
esquerdo da primeira regra, a menos que seja 
especificado ao contrário. 
2. Encontre uma variável que está escrita e uma 
regra que começa com aquela variável. Substitua 
a variável escrita pelo lado direito daquela regra. 
3. Repita o passo 2 até que nenhuma variável 
permaneça. 
Linguagem Livre de Contexto: qualquer linguagem que 
pode ser gerada por alguma gramática livre-de-contexto. 
Projetando Linguagens Livres-de-Contexto 
1. Muitas LLCs são a união de LLCs mais simples: 
construir uma GLC para um LLC, quebre em 
partes mais simples e construa gramáticas 
individuais para cada parte. 
2. Se a linguagem for regular, construa um AFD para 
ela.: Converta o AFD em GLC; Adicione a regra 
𝑅𝑖 → 𝑎𝑅𝑗 â GLC se 𝛿(𝑞𝑖, 𝑎) = 𝑞𝑖 for uma 
transição no AFD. Adicione a regra 𝑅𝑖 → 𝜀 se 
𝑞𝑖 for um estado de aceitação do AFD. Faça 𝑅0 
a variável inicial da gramatica, onde 𝑞0 é o 
estado inicial da máquina. Verifique se a GLC 
resultante gera a mesma linguagem que o AFD 
reconhece. 
3. Certas linguagens LLC precisam memorizar uma 
quantidade ilimitada de informação sobre uma 
subcadeia para verificar se é igual a outra: 
Construir uma GLC com uma regra da forma 
𝑅 → 𝑢𝑅𝑣, que gera cadeias nas quais a parte 
contendo os us corresponde à parte contendo 
os vs. 
4. Linguagens mais complexas, as cadeias podem 
conter estruturas recursivas: Coloque o símbolo 
da variável que gera a estrutura na posição das 
A → 0A1 
A → B 
B → # 
regras onde aquela estrutura pode aparecer 
recursivamente. 
Autômato com Pilha (AP) 
São um modelo computacional mais poderoso que 
autômatos finitos. 
↳Como autômatos finitos não-determinísticos mas têm 
um componente extra, a pilha. 
↳Pilha: provê memória adicional além da quantidade finita 
disponível no controle. Permite que o autômato 
reconheça alguma linguagens não-regulares. 
Autômatos de pilha são equivalentes em poder a 
gramáticas livres-de-contexto. 
Representação Esquemática 
↳Controle representa os estados e a função de 
transição; 
↳Fita contém a cadeia de entrada 
↳Seta aponta para o próximo símbolo de entrada a ser 
lido; 
↳Pilha representa memória extra., podendo guardar 
quantidade ilimitada de informação. 
Funcionamento: escreve símbolos sobre a fita e lê-os de 
volta mais tarde; 
• Escreve um símbolo e empurra para baixo todos 
os outros símbolos sobre a pilha. 
• Ultimo que entra primeiro que sai: apenas o topo 
pode ser lido e removido. 
• Empilhar: escrever um símbolo na pilha; 
• Desempilhar: remover um símbolo. 
Autômato com Pilha Não-Determinístico 
↳AP determinísticos e não determinísticos não são 
equivalentes em poder; 
↳Reconhecem linguagens que nenhum AP determinístico 
pode reconhecer; 
AP não-determinísticos são equivalentes em poder a 
GLC. 
Definição Formal: 
 
↪Autômatos com pilha e gramaticas livres-de-contexto 
reconhecem a mesma linguagem: linguagens livres-de-
contexto. 
Equivalência com Gramáticas Livres-de-Contexto 
 
↪Linguagem Regular é reconhecida por um autômato 
finito e todo autômato finito é automaticamente um 
autômato com pilha que simplesmente ignora sua pilha; 
↪Linguagem Regular é também uma linguagem livre-
de-contexto.