Linguagens Formais e
Compiladores
Carlos Alberto Pimentel
[email protected]
http://fragapimentel.googlepages.com
*Parte dos slides gentilmente cedidos pela prof Laís (Unifacs)
Ementa






Gramáticas e automatos
Gramáticas livres de contexto
Gramáticas sensíveis ao contexto
Introdução à arquitetura de
compiladores
Análise Léxica, sintática e semântica
Geração de código intermediário e
otimização
Habilidades





Conceituar gramáticas e automatos
Habilidade para diferenciar os diversos tipos
de gramáticas e automatos
Compreender as diversas fases de um
compilador
Habilidade para implementar um tradutor
Compreender como as diversas técnicas de
programação influenciam no desempenho dos
programas gerados.
Pré-requisitos

Conhecimentos básicos em teoria dos
conjuntos e lógica matemática
Conteúdo programático
Bibliografia






HOPCROFT, J., MOTOWANI, R. ULLMAN, J. Introduction to
Automata Theory, Languages and Computational. AddisonWesley, 2001.
AHO, A., SETHI, R. ULLMAN, J. Compilers. Addison Wesley,
2006.
LEWIS, H., PAPADIMITRIOU, C., Elements of the theory of
computational. Prentice Hall, 2004.
MENEZES, P., Linguagens formais e automatos. Sagra Luzzato,
2005. http://teia.inf.ufrgs.br/
PRICE, A. TOSCANI, S. Implementação de linguagens de
programação. Sagra Luzzato, 2005.
RAVI SETHI JEFFREY D. ULLMAN ET AL. Compiladores:
Princípios, Técnicos e Ferramentas.
Linguagens formais e
automatos


Originalmente desenvolvida em 1950
como estudo relacionado as linguagens
naturais, posteriormente linguagens
“artificiais”.
Emprego na análise léxica e sintática
das linguagens de programação.
Sintaxe e semântica


Linguagens formais preocupa-se com a
análise sintática.
A teoria da sintaxe possui modelos
matemáticos bem definidos. Ex.:
gramáticas de Chomsky

Linguagem: Uma entidade livre X
entidade com significado
Sintaxe e semântica


Sintaxe – Trata das propriedades livres
da linguagem. Ex.: Verificação
gramatical
Semântica – Objetiva dar uma
interpretação ou significado para o
programa
Alfabetos, palavras,
linguagens, gramáticas


Para o dicionário Aurélio um linguagem
é “O uso da palavra articulada ou
escrita como meio de expressão e
comunicação entre pessoas”
Precisamos de um formalismo
matemático.
Alfabeto




Um conjunto finito de símbolos.
{a, b, c, d, e, ..., z}
{0, 1}
{0, 1, 2, ..., 9, A, B, C, D, E, F}

Palavra, cadeia de caracteres
ou sentença





Uma seqüência finita de símbolos
justapostos.
Palavra vazia ε
Se
denota um alfabeto
* denota o conjunto de todas as
palavras sobre o alfabeto
+ denota o conjunto de todas as
palavras exceto palavra vazia. Exemplos???
Tamanho ou comprimento de
uma palavra






Sendo w uma palavra, o comprimento da
palavra é dado por |w|.
O comprimento é dado em número de
símbolos
|ε| = 0
|casa|=4
|pé|=2
|compilador|=?
Prefixo, sufixo, subpalavra





Prefixo – subconjunto inicial de símbolos
de uma palavra
Sufixo – subconjunto final de símbolos de
uma palavra
Subpalavra – qualquer subconjunto de
símbolos de uma palavra.
Abcb é uma palavra do alfabeto {a, b, c}
Exemplos de prefixo e sufixo????
Linguagem formal



Um conjunto de palavras sobre um
alfabeto.
Exemplo de linguagem: O conjunto de
palíndromos sobre um determinado
alfabeto
{}<>{ε}
Concatenação


Justaposição de símbolos que
representam as palavras componentes
Propriedades:


Associativa – v(wt) = (vw)t
Elemento neutro a esquerda e direita


εw=w=wε
Exemplos????
Concatenação sucessiva


Uma palavra e concatenada
sucessivamente com ela mesma.
wn – Sendo w uma palavra e n a
quantidade de contatenações. Assim:




w0=ε
wn= wn-1w, para n > 0
Ex.: A5=AAAAA
Concatenação da palavra vazia??????
Gramática


Uma gramática é uma quádrupla ordenada
G=(V, T, P, S)




V – Conjunto finito de símbolos não terminais
T – Conjunto finito de símbolos terminais
P – Conjunto finito de pares, denominados regras
de produção.
S – Elemento de V, denominado variável inicial
Regra de produção



Definem as condições de geração das
palavras da linguagem.
  1| 2 | 3| .... | n
Para descobrir se uma cadeia x 
T* é gerada pela gramática basta
fazer um processo de derivação
começando do símbolo inicial S até
obter a cadeia desejada.
Gramáticas
Um exemplo inicial:
<frase>
 <sujeito> <verbo> <predicado>
<sujeito>
 O homem
<sujeito>
 A mulher
<verbo>
 leu
<verbo>
 escreveu
<predicado>  um <adjetivo> livro
<adjetivo>  ótimo
<adjetivo>  péssimo
<adjetivo>  

Exemplo de gramática

A gramática gera a seguinte linguagem
 {ww | w é palavra de {a, b}*}
Gramática {ww | w é palavra de {a, b}*}





G={V, T, P, S}
V={S, X, Y, A, B, F}
T={a, b}
P={S→XY,
X→XaA | XbB | F,
Aa→aA, Ab→bA, AY→Ya,
Ba→aB, Bb→bB, BY→Yb,
Fa→aF, Fb→bF,FY→ }
S={S}
Exemplo de derivação da gramática {ww | w
é palavra de {a, b}*}

S=>XY=>XaAY=>XaYa=>XbBaYa=>X
baBYa=>FbaYba=>bFaYba=>baFYba
=>baba
{ww | w é palavra de {a, b}*}

A gramática apresentada gera o primeiro w
após X e o segundo w após Y, como segue:



A cada símbolo terminal gerado após X, é gerada
uma variável correspondente;
Esta variável “caminha” na palavra até passar por
Y, quando devira o correspondente terminal;
Para encerrar, X devira a variável F a qual
“caminha” até encontrar Y quando FY deriva a
palavra vazia.
Exercício (Media de eficiência)


Dada a gramática anterior da ling. {ww |
w é palavra de {a, b}*}
Gerar duas palavras de comprimento
|WW| = 4 e uma palavra de
comprimento |WW| = 6.
Mostrar que a palavra bbaa não pode
ser derivada da gramática.
Individual ou em dupla
Gramáticas equivalentes

Duas gramáticas G1 e G2 são ditas
Gramáticas equivalentes se, e somente
se, GERA(G1) = GERA(G2)
Exercício (Media de eficiência)


Desenvolver uma gramática que gere
expressões aritméticas com parênteses
balanceados, dois operadores
(representados por * e +) e um
operando (representado por x), Por
exemplo, x, x*(x+x) e ((((x)))) são
expressões aritméticas válidas.
No máximo 3 pessoas por equipe
Linguagens Regulares ou do
tipo 3

De acordo com a Hierarquia de
Chomsky, trata-se da classe de
linguagens mais simples, sendo possível
desenvolver algoritmos de
reconhecimento ou de geração de
pouca complexidade, grande eficiência
e de fácil implementação.
Propriedades das linguagens
regulares

LR podem ser representadas por formalismos




pouca complexidade
grande eficiência
fácil implementação
Entretanto, por ser uma classe relativamente
simples

é restrita e limitada
Linguagem Regular ou tipo 3

Uma das principais características das
linguagens regulares é o fato de serem
representadas for formalismos de pouca
complexidade, grande eficiência e fácil
implementação. Entretanto, por serem
de uma classe relativamente simples, é
restrita e limitada.
De acordo com a Hierarquia
de Chomsky
LR (tipo 3)
LSC
LLC
(tipo 2)
(tipo 1)
LEF (tipo 0)
Tradução dos formalismos das
linguagens regulares
Sistema de estados finitos

É um modelo matemático de um
sistema com entradas e saídas
discretas. Pode assumir um número
pré-definido de estados. Cada estado
resume somente informações do estado
passado para determinar as ações da
próxima entrada.
Exemplo de sistema de
estados finitos


Um exemplo clássico e simples é o elevador.
Trata-se de um sistema que não memoriza as
requisições anteriores. Cada “estado”
sumariza as informações “andar corrente” e
“direção de movimento”. As entradas para o
sistema são requisições pendentes.
Ou exemplo, analisadores léxicos e alguns
processadores de texto, memorizam apenas a
estrutura do prefixo das palavras
Teoria dos Autômatos
Autômatos Finitos
Autômatos finitos (AF):





-
modelo restrito para o computador
são dispositivos de reconhecimento de linguagens
tem capacidade finita fixa de informação
sem memória auxiliar
sem saída de dados
Pode-se dizer que é uma máquina abstrata que
reconhece linguagens. Supondo-se uma
linguagem L e fornecendo ao AF uma seqüência
de caracteres w, ele responderá se w  L ou w 
L.
Teoria dos Autômatos
Autômatos Finitos
Um autômato finito possui:

Fita de entrada – armazena os símbolos da
cadeia de entrada;

Controle finito - extrai símbolos da fita de
entrada através de um sensor de leitura;

Função de transição – decide qual deverá
ser o próximo estado do autômato, com
base no símbolo lido e no estado anterior;

Número finito de estados.
A Fita



É finita a esquerda e a direita, dividida
em células onde cada uma armazena
um símbolo.
Não é possível gravar sobre a fita e não
existe memória auxiliar
Inicialmente a cadeia a ser processada
ocupa toda fita
Unidade de controle



Possui um número finito de estados
pré-definido. A unidade lê um símbolo
da fita de cada vez e move a cabeça
para a direita
Inicialmente a cabeça é posicionada
mais a esquerda da fita.
Importante – O autômato Finito não
possui memória de trabalho.
Autômatos finitos equivalentes

Dois autômatos finitos M1 e M2 são ditos
equivalente se, e somente se:

ACEITAM(M1) = ACEITAM(M2)
Linguagem regular ou do tipo
3

Uma linguagem aceita por um autômato
finito determinístico é uma linguagem
regular
Teoria dos Autômatos
Autômatos Finitos
-
Graficamente um AF pode ser representado por
fita com a cadeia w de entrada
a
a
b
b
Cabeça
de leitura
Controle
Finito
Início do processo
de reconhecimento
pelo estado inicial qo
Teoria dos Autômatos
Autômatos Finitos
O Autômato Finito consegue ler, através da cabeça de
leitura, os símbolos da fita seqüencialmente sempre
da esquerda para a direita.
O AF é uma máquina que sempre pára retornando uma
resposta sim (cadeia reconhecida) ou não (cadeia
não conhecida).
Podem ser classificados em:
-
Autômatos Finitos Determinísticos (AFD)
Autômatos Finitos Não-Determinísticos (AFND)
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Definição formal de um Autômato Finito Determinístico:
Um Autômato Finito Determinístico (AFD) ou
simplesmente Autômato Finito (AF) M é uma 5-upla:
M = (, Q, , q0, F), onde
: alfabeto de símbolos de entrada;
Q: conjunto finito de estados do autômato;
: função programa ou função de transição (parcial)
: Q    Q
q0: estado inicial (q0Q)
F: conjunto de estados finais ou estados de aceitação (FQ)
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Representação Gráfica:
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Exemplo: Autômato que reconhece a linguagem de
números binários com quantidade ímpar de 1s.
M = (∑, Q, , qo, F)
Q = { qo, q1 }, ∑ = { 0, 1 }, F = { q1 }
Forma Tabular :
Forma Gráfica :
1

0
1
qo
qo
q1
q1
q1
qo
0
0
q1
qo
1
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Um Autômato Finito nunca entra em “loop”
infinito, pois como qualquer cadeia a ser
processada pelo AF é finita e como um novo
símbolo da entrada é lido a cada aplicação
da função programa, o processo de
reconhecimento de qualquer cadeia  pára
de duas maneiras:



Aceitando ou;
rejeitando uma entrada .
Teoria dos Autômatos
Autômatos Finitos Determinísticos
As condições de parada são as seguintes:

Após processar o último símbolo da fita, o Autômato
Finito assume um estado final: o autômato pára e a
entrada  é aceita;

Após processar o último símbolo da fita, o AF
assume um estado não final: o autômato pára e a
entrada  é rejeitada;

A função programa é indefinida para o argumento
(estado corrente, símbolo lido): a máquina pára e a
palavra de entrada  é rejeitada.
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Definição: Autômatos Finitos equivalentes.

Dois autômatos finitos M1 e M2 são ditos
equivalentes se, e somente se: L(M1) =
L(M2);
Definição: Um linguagem aceita
autômato finito determinístico
linguagem regular ou Tipo 3.
por um
é uma
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Exemplo: Autômato que reconhece a linguagem de
números binários com quantidade ímpar de 1s.
M = (∑, Q, , qo, F)
Q = { qo, q1 }, ∑ = { 0, 1 }, F = { q1 }
Forma Tabular :

0
Forma Gráfica :
1
1
qo
qo
q1
q1
q1
qo
0
0
q1
qo
1
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Definição: Processo de reconhecimento de uma dada
cadeia w por um AF.
O autômato é inicializado com a cabeça no símbolo
mais a esquerda e no estado inicial qo. Se um AF
M=(∑, Q, , qo, F) está no estado p e a cabeça de
leitura da fita olha o símbolo a  ∑, então o AF
vai para o estado (p, a) = q e move a cabeça
um símbolo à direita.
Se w  ∑* então M aceita w se M computa w e
depois de ler o último símbolo de w entra em um
estado final  F.
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Seja a cadeia w = 01110. Deseja-se verificar se w é
reconhecida pelo AFD do exemplo anterior.
(q0, 0) = q0
(q0, 1) = q1
0 1 1 1 0
(q1, 1) = q0
0 1 1 1 0
Cabeça
de leitura
Controle
Finito
Início do
AFD em q0
0 1 1 1 0
Cabeça
de leitura
Controle
Finito
q0
(q1, 0) = q1
(q0, 1) = q1
Cabeça
de leitura
Cabeça
de leitura
Controle
Finito
q0
q1
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
Cabeça
de leitura
Controle
Finito
Controle
Finito
q1
Cabeça
de leitura
Controle
Finito
q1  F
Como ao final da leitura da cadeia w o estado que o AFD assumiu foi q1  F então a
cadeia w é reconhecida pelo autômato, ou seja, w é aceita como uma cadeia da
linguagem reconhecida pelo AFD.
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Exemplo 1: Construir um AFD que reconhece a
linguagem a*.
M = (∑, Q, , qo, F)
Q = { qo }, ∑ = { a }, F = { q0 }
Forma Tabular :

a
qo
qo
Forma Gráfica :
a
qo
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Exemplo 2: Construir um AFD que reconhece a
linguagem aa* .
M = (∑, Q, , qo, F)
Q = { qo, q1 }, ∑ = { a }, F = { q1 }
Forma Tabular :

a
qo
q1
q1
q1
Forma Gráfica :
a
qo
a
q1
Teoria dos Autômatos
Autômatos Finitos Determinísticos
Exemplo 3: Construir um AFD que reconhece a
linguagem (abb*a)* .
M = (∑, Q, , qo, F)
Q = { qo, q1, q2 }, ∑ = { a, b }, F = { q0 }
Forma Tabular :

a
b
qo
q1
qrej
q1
qrej
q2
q2
q0
q2
Forma Gráfica :
a
qo
q1
b
a
b
q2
Obs.: qrej é o estado que representa a rejeição de um
símbolo de uma dada cadeia w, ou seja, w 
Linguagem reconhecida pelo AFD.
Exercícios

Construa um autômato finito determinístico e uma expressão
regular para cada umas da linguagens a seguir:
 A) A linguagem dos identificadores do pascal



B) Os números inteiros



Ex. válidos: a, _, media, M23af, c311
Ex. inválidos: 2, 45media, 3csa
Ex. válidos: 1, -1, +1, +45, 77, -44, 4564894, -459456
Ex. inválidos: +, -, 55+5, 8989-4, --65, ++5
C) Os números reais


Ex. válidos: 1, -1, +1, +45.05, 77.5, -44.5554, 4564.894, -459456
Ex. inválidos: +, -, 55+5, 8..989-4, --65, ++5, .56, +.45, .564, -+532
Teoria dos Autômatos
Expressões Regulares


A expressão regular é a maneira mais compacta
e mais simples de descrever conjuntos regulares,
e é usada com essa finalidade em construção de
compiladores, editores, sistemas operacionais,
protocolos, etc.
É
um
formalismo
considerado gerador.
denotacional,
também
Expressão Regular ER


Toda linguagem regular pode ser
descrita por uma expressão regular
simples, denominada Expressão regular.
Trata-se de um formalismo
denotacional, também considerado
gerador, pois pode-se inferir como
construir (“gerar”) as palavras de uma
linguagem.
Como saber se uma
linguagem é regular



Basta representá-la com pelo menos um
dos seguintes formalismos
{autômato finito | Expressão Regular |
Gramática Regular}
Para mostrar que uma linguagem não é
regular é preciso mostrar que ele não poder
ser representada por nenhum dos
formalismos. Pode-se usar o Lema do
bombeamento.
Expressão Regular ER


A omissão de parênteses em uma ER
sobre um alfabeto é indutivamente
definida como se segue:
Uma linguagem gerada por uma ER r é
representada por L(r) ou GERA(r).
Expressões Regulares
Definição: Uma Expressão Regular (ER) sobre um
alfabeto  é definida como segue:

 é uma ER (linguagem vazia)

 é uma ER (linguagem contendo somente a
cadeia vazia )

para cada a  , a é uma ER

se  e  são ER´s, então | é uma ER. ( OU  –
alternância)

se  e  são ER´s, então  é uma ER.
(concatenação)

se  é uma ER, então ()* é uma ER
(exponenciação)
Teoria dos Autômatos
Expressões Regulares




*:  |  |  |  |.....
+:  |  |  |.....
+ = *
ordem de precedência(decrescente):

exponenciação

concatenação

alternância
Teoria dos Autômatos
Expressões Regulares
Expressão regular
Linguagem representada
aa
Somente a palavra aa
ba*
Todas as palavras que começam com b, seguido por
zero ou mais a´s
(a|b)*
Todas as palavras sobre {a, b}
(a|b)* aa (a|b) *
Todas as palavras que contém aa como subpalavra
a* ba* ba*
Todas as palavras contendo exatamente 2 b´s
(a|b)* (aa| bb )
Todas as palavras que terminam com aa ou bb
(a| ) (b | ba)*
Todas as palavras que não possuem 2 a´s
consecutivos
Exercício


Desenvolva Autômatos Finitos
Determinísticos, que reconheçam as
seguintes linguagens:
A) sobre o alfabeto {a, b, c}

{w | aa ou bb é subpalavra e cccc é sufixo
de w}
Exercícios

b) Sobre o alfabeto {a, b}


b1) {W1W2W1 | W2 é qualquer e |W1| = 3}
b2) {W | o décimo símbolo da direita para
a esquerda de w é a}
Autômato finito não
determinístico

O não determinismo é uma importante
generalização dos modelos de
máquinas, sendo e fundamental
importância no estudo da teoria da
computação e na teoria das linguagens
formais.
Autômato finito não
determinístico – AFN ou AFND

Nem sempre a facilidade do nãodeterminísmo aumenta o poder de
reconhecimento de linguagens de uma
classe de autômatos
Importante


Qualquer autômato finito nãodeterminístico pode ser simulado por
um autômato finito determinístico.
Assim, para cada AFN é possível
construir um AFD equivalente que
realiza o mesmo processamento.
A facilidade do não
determinismo


A função programa, ao processar uma
entrada composta pelo estado corrente
e símbolo lido, tem como resultado um
conjunto de novos estados.
O não-determinísmo.

Ilustração: Filme “O Vidente”
Aceitação do AFN

Um linguagem é aceita pelo autômato
finito não determinístico é denotada por
ACEITAM(M) ou L(M), é o conjunto de
todas as palavras pertencentes a
* tais
que existe pelo menos um caminho
alternativo que aceita a palavra.
Autômato finito com
movimentos vazios AFNε




Movimentos vazios constituem uma
generalização dos modelos de máquinas nãodeterminísticas.
Um movimento vazio é uma transição sem
transição.
Uma das vantagens dos momentos vazios é
que facilita algumas demonstrações
relacionadas com os autômatos.
A facilidade dos momentos vazios não
aumentam o poder de reconhecimento
Equivalência entre ER e AFD
Gramática linear

Seja G=(V, T, P, S) uma gramática e
sejam A e B elementos de V e w uma
palavra de T*. Então G é uma:

Gramática Linear à direita (GLD). Se todas
as regras de produção são da forma:


A→wB ou A→w
Gramática Linear à esquerda (GLE). Se
todas as regras de produção são da forma:

A→Bw ou A→w
Gramática linear

Gramática Linear Unitária à direita (GLUD).
Se todas as regras de produção são da
forma:


A→wB ou A→w, adicionalmente |w|<=1
Gramática Linear à esquerda (GLUE). Se
todas as regras de produção são da forma:

A→Bw ou A→w, adicionalmente |w|<=1
Equivalência das gramáticas
lineares


As diversas gramáticas lineares são
formalismos equivalentes:
Seja L uma linguagem então:




Lé
Lé
Lé
se,
Lé
gerada por uma GLD se, e somente se,
gerada por uma GLE se, e somente se,
gerada por uma GLUD se, e somente
gerada por uma GLUE.
Ex. de gramáticas lineares
equivalentes para a linguagem a(ba)*
GLD para a linguagem a(ba)*


G={{S,A}, {a,b}, P, S}
P={S→aA,
A→baA|}
GLE para a linguagem a(ba)*


G={{S}, {a,b}, P, S}
P={S→Sba|a}
GLUD para a linguagem
a(ba)*


G={{S,A, B}, {a,b}, P, S}
P={S→aA,
A→bB|,
B→aA}
GLUE para a linguagem a(ba)*


G={{S,A}, {a,b}, P, S}
P={S→Aa|a,
A→Sb}
Teorema


1 - Se L é uma Linguagem gerada por
uma gramática regular, então L é
uma linguagem regular
2 - Se L é uma linguagem regular,
então existe uma gramática regular
G que gera L.
Linguagens Livres de Contexto

Segundo a classificação realizada por
Chomsky nem todas as linguagens
livres de contexto são regulares. Isto
ocorre porque elas possuem cadeias
com construções contendo
“aninhamento sintático”.
Linguagens Livres de Contexto

Possuem aninhamento Sintático.
Exemplo:

L = { w | w  conjunto de
cadeias com número balanceado de
parênteses escritos em ordem correta }


x = (( )( ))( ), y = ((( ))),
z = ( )(( )( ))(( ))
Linguagens Livres de Contexto


Compreende um universo mais amplo de
linguagens (comparativamente com as
regulares) tratando, adequadamente,
parênteses balanceados, construções blocoestruturadas, dentre outras
Os conceitos da LLC são aplicados aos
analisadores sintáticos, tradutores de
linguagens e processadores de texto em geral
Gramática Livre de contexto


Gramática onde as regras de produção
são definidas de forma mais livre que
na Gramática Regular.
São entidades geradoras de Linguagens
Livres de Contexto
Autômato com pilha


Autômato cuja estrutura básica é
análoga à do Autômato Finito,
adicionando uma memória auxiliar tipo
pilha (a qual pode ser lida ou gravada)
O autômato com pilha pode ser
Determinístico ou não-Determinístico
De acordo com a Hierarquia
de Chomsky
LR (tipo 3)
LSC
LLC
(tipo 2)
(tipo 1)
LEF (tipo 0)
Exemplos de linguagens livres
de contexto
a) L = { wwr, onde w é uma seqüência de símbolos
do Vt, e wr é o inverso de w }, Ex.: Vt={ a, b}, x
= abba, y = abbaaaabba, z = bbabbabb
b) L = { wcwr, onde w é uma seqüência de
símbolos de Vt, e c  Vt }, Ex.: Vt={ a, b, c}, x
= abcba, y = abbaacaabba, z = bbabcbabb
c) L = { anbn, n >= 0 }, Ex.: x = aabb, y =
aaaaabbbbb, z = 
d) L = { w  { a, b }*, com o mesmo no de a´s e
b´s }, Ex.: x = abaabb, y = aabb, z = bbaaab
Problema
Pensando nas cadeias geradas pelas Linguagens
Livres de contexto não regulares parece que
qualquer dispositivo que as reconheça, necessita
“lembrar” de características da cadeia analisada.
No exemplo do item b, supondo Vt = { a, b, c } e a
cadeia de entrada
aabbbacabbbaa
deve existir um esquema para “lembrar” a primeira
metade da cadeia de entrada (antes de c) para
poder verificar a outra metade na ordem inversa.
Constatação: O Autômato Finito
não possui este recurso !!!

Análise:


Se a máquina fosse capaz de acumular os
símbolos da cadeia de entrada, utilizando uma
MEMÓRIA auxiliar, à medida que a cadeia é lida e
pudesse retirar estes símbolos da MEMÓRIA
quando necessário o processo de reconhecimento
seria resolvido.
Solução:

O dispositivo que soluciona parte deste problema
é uma PILHA, funcionando como MEMÓRIA, que
permite o acesso de leitura (pop) e gravação
(push).
Graficamente um Autômato de
Pilha pode ser representado por:
fita com a cadeia w de entrada
a
a
b
b
b
a
c
a
b
b
b
a
Cabeça
de leitura
e gravação
Cabeça
de leitura Controle
Finito
qi
Início do processo de reconhecimento
pelo estado inicial qo
a
b
b
a
a
Pilha
Autômato com pilha

O Autômato de Pilha (AP) consegue ler,
através da cabeça de leitura, os
símbolos da fita seqüencialmente
sempre da esquerda para a direita,
armazenar (push) e retirar (pop)
símbolos da Pilha.
Pilha do Autômato
O Autômato de Pilha (AP) é
uma 7-upla:

O Autômato de Pilha (AP) é uma sétupla:


M = (E, Q, P, F, q0, z0, V)
Onde:







E é o alfabeto dos símbolos de entrada que podem formar a
cadeia w є V* da fita
Q é um conjunto finito (não vazio) de estados.
P função programa ou função transição
q0 é o estado no qual o autômato é iniciado, q0 є Q.
F é o conjunto de estados finais (reconhecedores).
z0 é o símbolo inicial da pilha.
V é o alfabeto de símbolos finito da pilha.
{anbn | n>= 0}
{WWr | w pertence a {a, b}*}
{anbman+m | n >= 0, m>= 0}