WILSON ROSA DE OLIVEIRA
Departamento de Estatística e
INFORMÁTICA
UFRPE
http://www.cin.ufpe.br/~wrdo/
Objetivo
Dar aos alunos noção formal de
algoritmo, computabilidade e do
problema de decisão, de modo a
deixá-lo consciente das
limitações da ciência da
computação.
Aparelhá-los com as ferramentas de
modo a habilitá-lo a melhor
enfrentar a solução de problemas
com o auxílio do computador.
Dar subsídios para os alunos
poderem definir linguagens de
programação, isto é, sua sintaxe
e semântica, através do estudo
das gramáticas formais.
Ementa
Autômatos: Finitos, a Pilha e
Máquina de Turing (linearmente
limitada).
Linguagens Formais: Regular, Livre
e Sensível ao Contexto,
Estrutura de Frases.
Hierarquia de Chomsky.
Aplicações em compiladores.
Computabilidade: modelos
computacionais (funções
recursivas, linguagens de
programação), funções não
computáveis, problema da
parada, decidibilidade.
Bibliografia
• Introdução à Teoria de Autômatos, Linguagens e
Computação. John E. Hopcroft, Jeffrey D. Ulman e
Rajeev Motwani. Trad. da segunda edição, Editora
Campus. (Livro Texto)
• Acióly, Benedito M.; Bedregal, Benjamín R. C.; Lyra,
Aarão. Introdução à Teoria das Linguagens Formais, dos
Autômatos e da Computabilidade. Edições UnP, 2002.
• BIRD, Richard. Programs and Machines - an introduction to
the theory of computation. London: John-Wiley, 1976.
• BRAINERD,W. S.; LANDWEBER L. H. Theory of
Computation. New York: Wiley, 1974.
• DIVERIO, Tiaraju A.; MENEZES, Paulo F. Blauth. Teoria da
Computação – Máquinas Universais e Computabilidade. 2a.
Edição. Porto Alegre: Sagra-Luzzatto, 2000. 205p.
Bibliografia
• HOPCROFT, J.; ULLMAN, J. Introduction to Automata
Theory, Languages and Computation. Addison-Wesley,
1979.
• LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de Teoria
da Computação 2a. Edição. Bookman. 2000. 361p.
• Menezes, P.F.B. LINGUAGENS FORMAIS E AUTÔMATOS.
Série Livros Didáticos. Instituto de infromática da UFRGS. (
3 Edição). ISBN 85-241-0554-2
• MANNA, Zohar. Mathematical Theory of Computation. New
York: McGraw-Hill, 1974.
• SERNADAS, C. Introdução à Teoria da
Computação. Lisboa: Editorial Presença, 1993.
Avaliação
DATA DAS PROVAS:
•
•
•
•
1a. VA: 26/09/2005 (segunda);
2a. VA: 21/11/2005 (segunda);
3a. VA: 05/12/2005 (segunda);
Final: 19/12/2005 (segunda);
Motivação
O objetivo do curso é entender os
fundamentos da computação.
• O que significa uma função ser
computável
• Existem funções não - computáveis
• Como a capacidade computacional
depende das estruturas de
programação
Conceitos
• Estado
• Transição
• Não - Determinismo
• Redução
Modelos de Computação
•Autômato Finito, Expressões Regulares
•Autômato a Pilha
•Autômatos Lineares Limitados
•Máquinas de Turing
Hierarquia de Chomsky
•Linguagens e Gramáticas
•Linguagens e Gramáticas
•Linguagens e Gramáticas
•Linguagens e Gramáticas
Regulares
Livre de Contexto
Sensível ao Contexto
sem Restrição
Definições Preliminares
Símbolo - letras e dígitos
Alfabeto - Conjunto finito de símbolos
Ex:  = { 0,1,2,…,9}
 = {a,b,c,…,z}
 = {0,1 }
cadeia (string) (sobre ): qualquer
seqüência finita de elementos de .
Ex.:  = { a,b }
aabab, bb, abab
Notação: x, y, z.
tamanho de uma Cadeia x é o número de
símbolos em x.
Notação: | x |
Ex: | aabab | = 5
| abab | = 4
Cadeia Vazia : e ou λ
|λ|=0
a n Significa uma cadeia de a ‘s de
tamanho n.
Ex.: a5 = aaaaa
a1 = a
a0 = λ
Concatenação de x com y é gerar uma cadeia
xy colocando x junto
de y.
obs.: xy yx
Ex:
x = aa
y = bb
xy = aabb yx = bbaa
Propriedades da
Concatenação
Monóide
Associatividade
(xy) z = x (yz)
Identidade da Cadeia Vazia
λx=xλ=x
|xy| = | x| + | y|
aman = am+n
 m,n  0
OPERAÇÕES SOBRE CADEIAS
 * é o conjunto de todas as cadeias sobre
o alfabeto  .
Ex.:
{a,b}* = {e,a,b,aa,ab,ba,bb,…}
{ a }* = {λ,a,aa,aaa,aaaa,…}
= { a n | n  0}.
f é o conjunto vazio.
f * = {λ} por definição.
Diferença entre cadeias e
conjuntos.
• {a,b} = {b,a}, mas ab  ba
• {a,a,b} = {a,b}, mas aab  ab
• f  conjunto com nenhum elemento;
vazio.
• {λ}  conjunto com 1 elemento, a cadeia
vazia.
• λ  cadeia vazia, que não é conjunto.
ESTADO
•O Estado de um sistema é uma descrição
do sistema;
• uma fotografia da realidade congelada no
tempo.
•Um estado dá todas as informações
relevantes necessárias para determinar
como o sistema pode evoluir a partir
daquele ponto.
TRANSIÇÕES
• São mudanças de Estados:
• Expontâneas
• Em resposta a uma entrada externa
• Instantâneas
• Exemplos de sistemas de transições de
estado:
•
•
•
•
Circuitos Eletrônicos
Relógios Digitais
Elevadores
O jogo da vida
Sistemas de Transições de
Estados Finitos:
• Consiste de somente vários estados
finitos e transições sobre estes
estados.
• Modelado através de Autômatos Finitos
AUTÔMATOS FINITOS
autômato finito determinístico :
M = (Q, , d, s0, F), onde:
• Q é um conjunto finito; os elementos de Q são
chamados os estados;
•  é um conjunto finito; o alfabeto de entrada;
• d : Q x   Q é a função de transição. Se M
estar no estado Q e vê a entrada a, o
autômato vai para o estado d (q,a);
• s0  Q é o estado inicial;
• F  Q; os elementos de F são os estados finais
ou estados de aceitação.
EXEMPLO 1
M = (Q, , d, q0, F)
Q = {q0, q1, q2, q3 }
 ={ a, b}
d(q0,a) = q1
d(q1,a) = q2
d(q2,a) = d (q3,a) = q3
d(q,b) = q ; q  { q0, q1, q2, q3 }
F = { q3 }
TABELA DE TRANSIÇÃO
Estados
q0
q1
q2
q3 F
Entradas
a
b
q1
q0
q2
q1
q3
q2
q3
q3
DIAGRAMA DE TRANSIÇÃO
b
q0
a
a
q1
a, b
b
b
q2
a
q3
x  L(M)
x = baaba
d(q0,b) = q0
d(q0,a) = q1
d(q1,a) = q2
d(q2,b) = q2
d(q2,a) = q3
q3  F  X  L(M)
x  L(M)
x = bbaba
d(q0,b) = q0
d(q0,b) = q0
d(q0,a) = q1
d(q1,b) = q1
d(q1,a) = q2
q2  F  X  L(M)
EXEMPLO 1
•
•
•
•
M estará no
M estará no
M estará no
M estará no
mais a’s.
estado
estado
estado
estado
q0
q1
q2
q3
ao ver nenhum a
ao ver um a
ao ver dois a’s
ao ver três ou
FUNÇÃO DE TRANSIÇÃO
GENERALIZADA
d* : Q x *  Q
d*(q, ) = q
(1)
d*(q, xa) =d (d*(q,x), a) (2)
• d* Mapeia um estado q e uma cadeia x em
um novo estado d*(q, x).
• d* É uma versão de múltiplos passos de d .
observações
•Eq.1 é a base da indução e diz que sem ler
um símbolo de entrada o autômato não pode
mudar de estado.
•Eq. 2 é o passo da indução e diz como
encontrar o estado depois de ler uma cadeia
não-vazia xa .
• encontre o estado, p = d*(q, x), depois de ler x
e compute o estado d(p, a).
d* e d são iguais em cadeias de tamanho 1.
 d*(q,a)= d*(q, a)
•
= d(d*(q,), a)
•
= d(q,a)
a = a
por 2, x=
por 1.
ACEITAÇÃO DE CADEIAS
•uma cadeia x é aceita por M se
d*(s0, x)  F
•e rejeitada por M se
d*(s0, x)  F
• conjunto ou linguagem aceita por M
L(M) = { x  * | d* (s0, x)  F}
•A  * é REGULAR se A = L(M) para
algum autômato finito M.
• {x  {a,b)* | x contém pelo menos três a’s} é
um conjunto REGULAR.
EXEMPLO 2
M = (Q, , d, q0, F)
Q = {q0, q1, q2, q3
 = {0, 1}
F = {q0 }
x = 110101
q0F
q1
q2
q3
0
q2
q3
q0
q1
1
q1
q0
q3
q2
d (q0 ,1) = q1
d (q1 ,1) = q0 d* (q0, 11) = q0
d (q0 ,0) = q2 d* (q0, 110) = q2
d (q2 ,1) = q3 d* (q0, 1101) = q3
d (q3, 0) = q1 d* (q0, 11010)=q1
d (q1 ,1) = q0 d* (q0, 110101)=q0
q0  F  x  L(M)
EXEMPLO 2
•L(M) é o conjunto de cadeias com um
número par de zeros e um número par de
uns.
1
q0
q1
0
1
0
0
01
q2
q3
1
EXEMPLO 3
Considere o conjunto {xaaay | x,y  {a,b}*}
q0
q1
q2
q3 F
a
q1
q2
q3
q3
b
q0
q0
q0
q3
baabaaab  L(M)
babbabab  L(M)
EXEMPLO 3
a, b
b
q0
a
b q1
b
a
q2
a
q3
• Usar os estados para contar o número de a’s
consecutivos que vimos. Se você não viu 3 a’s
consecutivos e você vê um b, volte para o
começo. Uma vez visto 3 a’s consecutivos
permaneça no estado de aceitação.
EXEMPLO 4
•Considere o conjunto {x  {0,1}* | x representa um
múltiplo de 3 em binário}.
• zeros na frente são permitidos
  representa o número zero
binário
0
11
110
1001
1100
1111
10010
decimal
0
3
6
9
12
15
18
EXEMPLO 4
1
0
q0
1
0
q1
0
q2
1
Propriedades das
Linguagens Regulares
• Para A, B  * temos as seguintes
definições:
A  B = { x | x  A ou x  B}
A  B = { x | x  A e x  B}
~A = { x  * | x  A}
• Mostraremos que para A e B regulares:
• A  B, A  B e ~A também são regulares.
A Construção do Produto
• Assuma que A e B são regulares, logo
existem autômatos
M1 = (Q1, , d1, s1, F1)
M2 = (Q2, , d2, s2, F2)
com L(M1) = A e L(M2) = B
• Para mostrar que A  B é regular, vamos
construir o autômato M3 tal que
L(M3) = A  B .
Intuitivamente ...
• M3 terá os estados de M1 e M2 codificado
de alguma maneira no seus estados.
• Para uma entrada x  *, M3 simulará
M1 e M2 simultaneamente em x,
aceitando x se somente se ambos M1 e
M2 aceitarem.
Intuitivamente ...
• M3 terá os estados de M1 e M2 codificado
de alguma maneira no seus estados.
• Para uma entrada x  *, M3 simulará
M1 e M2 simultaneamente em x,
aceitando x se somente se ambos M1 e
M2 aceitarem.
Formalmente ...
• Seja
M3 = (Q3 , ,d3, s3, F3 ) onde
Q3 = Q1 x Q2 = { (p,q) | p  Q1 e q Q2 }
F3 = F1 x F2 = { (p,q) | pF1 e qF2}
s3 = (s1,s2)
d3 : Q3 x   Q3 a função transição definida por:
d3 ( (p,q), a) = (d1(p,a), d2(q,a))
d3* ((p,q)), e ) = (p,q)
d3* ((p,q)), xa) = d3 (d3*((p,q),x),a)
Lema: Para todo x  *,
d3* ((p,q)), x) = (d*1(p,x), d*2((q, x))
Prova: Por indução em |x|
Base: Para |x| = 0, i.e., x =
e
d*3 ((p,q)),e) = (p,q) = (d*1(p,e), d*2 ((q,e)) .
Passo: Assumindo que o lema é válido para x*,
mostraremos que é válido para xa, onde a  .
d*3 ((p,q)), xa) = d3 (d3* ((p,q), x), a) Def. de d3*
= d3 ( (d1*(p, x), d2* (q, x) ), a) hipótese da ind.
= (d1 (d1* (p, x), a), d2* (d2 (q, x) a) Def. de d3
= (d1* (p, xa), d2* (q, xa) ) Def. de d1* e d2*
q.e.d.
Teorema. L(M3) = L(M1)  L(M2)
Prova: Para todo x  *, x  L(M3)
 d3* (s3, x)  F3
definição de aceita
 d3* ((s1,s2),x)  F1 x F2 definição de s3 e F3
 (d1* (s1,x),d2*(s2,x))  F1 x F2 lema
 d1*(s1,x)F1, e d2*(s2,x)F2 definição do x
 x  L(M1) e x  L(M2) def. de aceita.
 x  L(M1)  x  L(M2) def. de interesse
q.e.d.
• Para mostrar que ~A é Regular:
• Tome o autômato aceitando A e torne os
estados finais com os não-finais. O autômato
resultante aceita exatamente o que o
autômato original rejeita, logo o conjunto ~A
• A  B = ~ ( ~A  ~B)
AUTÔMATO FINITO
NÃO-DETERMINÍSTICO
• O próximo estado não é necessariamente
unicamente determinado pelo estado
atual e pelo símbolo de entrada.
• Podemos ter zero, uma ou mais
transições de estado com o mesmo
símbolo de entrada.
Exemplo 1:
A = { x  {0, 1}* | o quinto símbolo da
direita para esquerda é 1}
0,1
q1
1
0,1
q2
11010010  A
0,1
0,1
q3
q4
0,1
q5
q6
11000010  A
Não - determinístico:
- q1 tem duas transições com o símbolo 1.
- q6 não tem transições.
Exemplo 2
0,1
q0
0
q3
0
q4
0,1
1
q1
1
q2
0,1
q0 tem duas transições com 0 e
duas com 1
q1 não tem transição com 0
q3 não tem transição com 1
Exemplo 2 (cont.)
• Uma seqüência de entrada a1a2 …an é
aceita por um autômato finito não
determinístico se existe uma seqüência de
transições, correspondendo a seqüência de
entrada, que leva do estado inicial algum
dos estados finais.
• 01001 é aceita por este autômato pois a
seqüência de transições é q0 q0 q0 q3 q4 q4
• aceita todos as cadeais com dois 1’s ou
dois 0’s consecutivos.
Obs.: Autômatos determinísticos são um caso
especial de autômatos não determinísticos.
q0
0
0
q0
q3
1
1
q0
q1
q0
0
0
q3
0
0
0
q0
q3
q4
1
1
0
q0
q1
q4
Definição: Um autômato finito não determinístico (AFND) é uma 5 - upla
(Q,,d,q0,F) onde Q, , q0, e F tem o
mesmo significado que para autômato
finitos determinísticos (AFD) e d é um
mapeamento de Q x   2Q.
d (q, a) é o conjunto de todos os estados p
tal que existe uma transição (com o
símbolo a) de q para p.
A função d
abaixo.
Estado
q0
q1
q2
q3
q4
do autômato anterior é dada
Entrada
0
{q0,q3}
f
{q2 }
{q4 }
{q4 }
1
{q0, q1}
{q2 }
{q2 }
f
{q4 }
d* : Q x *  2Q
1) d*(q,e) = {q}
2) d*(q,wa) = { p | para algum rd*(q,w),
pd (r, a)}
Começando em q e lendo a cadeia w
seguida do símbolo a nós podemos estar
no estado p sss um estado possível de se
estar após ler w é r e de r podemos ir
para p lendo a.
X = 01001
d (q0 , 0) = {q0, q3 }
d (q0, 01) = d (d (q0, 0), 1)
= d ( {q0, q3}, 1)
= d (q0 ,1)  d (q3,1)
= { q0, q1}
d (q0, 010) = { q0, q3 }
d (q0, 0100) = {q0, q3, q4 }
d (q0, 01001) = {q0, q1, q4 }
autômatos finitos com
transições e
e
p
q
o autômato vai do estado p para o
estado q sem ler um símbolo de
entrada.
EXEMPLO 1
s
b
e
t
e
p
b
e
u
e
q
b
r
Estando no estado s e recebendo o símbolo b:
• ler b e ir para p
• ir para t e então ler b e ir para q
• ir para t, ir para u e então ler b e ir para r.
O conjunto aceito pelo autômato acima é
{b, bb, bbb}.
EXEMPLO 2
e
eq1
a
q2 a
q3
a
a
q4
a q6
a
q5
a
q8
a
q7
q9
O conjunto aceito pelo autômato acima é { x
 {a*} | |x| é divisível por 3 ou 5}.
A maior vantagem de transições e é a
conveniência.
Autômato com transições e tem o mesmo
poder computacional que afds e afnds
Propriedades de
Linguagens Regulares
Concatenação de dois conjuntos A e B
A•B = AB = { xy | x  A e y  B}
EXEMPLO.
{a, ab} • {b, ba} = {ab, aba, abb, abba}
Se A e B são conjuntos regulares, AB
também é.
Prova Intuitiva
Seja M o autômato para A e N para B.
• Construir um novo autômato P cujo os
estados são a união dos de M e N.
• Todas as transições de M e N serão
transições de P.
• O estado inicial de M será o de P.
• Os estados finais de N serão os de P.
• Finalmente, ligue os estados finais de M ao
estado inicial de N com uma transição e.
EXEMPLO 4
Seja A = {aa}, B = {bb}
q0
q0
a
a
q1
q1
a
q2
a
q3
q2
e
q3
b
b
q4
q4
b
b
q5
q5
Fecho de Kleene
Se A é regular então A* também é.
A* = { e}  A  A2  A3  …
= { x1x2…xn | n  0 e xiA , 1  i  n}
Prova Intuitiva
Seja M o autômato para A então P para A*
é como segue:
•
•
•
•
Comece com todos os estados e
transições de M.
Adicione um novo estado q e uma
transição e de q para o estado inicial de
M. Faça q o estado inicial de P.
Faça q o único estado final de P.
Adicione transições e dos estados finais de
M para o estado q.
EXEMPLO 5
Dado o autômato para A
e
q
a
q0
e
{aa}, o para A* :
a
q1
q2
Casamento de Padrões e
Expressões Regulares
O que acontece quando digitamos
‘rm *’ no Unix? E ‘rm *.dvi’?
Casamento de padrões é uma aplicação
importante da teoria dos afds.
Seja  um alfabeto finito.
Um padrão é uma cadeia de símbolos de
um certo formato representando um
conjunto (possivelmente infinito) de
cadeias sobre *.
Casamento de Padrões
Padrões: Básicos
Compostos
Notação: letras gregas a , b , g , …
Associado a definição de padrões, temos
quais cadeias x  * casam com os
padrões definidos.
Notação: L(a) é o conjunto de cadeias em
* que casam um dado padrão a. L(X) =
{x  * | X casa com a }
Padrões Básicos
•
a para cada símbolo a  , L(a) = {a}

e casa com a palava vazia e,L(e) = { e }

•
•
f casa com nada, L(f) = f, o cjto.vazio
# casa com qualquer símbolo em , L(#) = 
@ casa qualquer cadeia em *, L(@)=*.
Padrões compostos
• São formados indutivamente usando os
operadores: +, , * , ~ , •
• Suponha que definimos os conjuntos de
cadeias L(a) e L(b) casando a e b
respectivamente. Então dizemos:
• x casa com a + b , se x casa ou com a ou
com b
L(a + b ) = L(a )  L(b)
X casa com a  b se X casa com ambos a e
b
L(a  b ) = L(a)  L(b)
• X casa com ab se existem cadeias y e z tal
que y casa com a, z casa com b e x = yz.
L(ab) = L(a)•L(b)
• X casa ~a se X não casa com a.
L(~a) = ~ L(a ) = * \ L(a)
Esta definição depende de .
•
X casa a* se x pode ser dividido na
concatenação de várias (talvez nenhuma)
cadeias finitas, x=x1x2x3…xn, n 0 tal que
cada xi casa com a.
L(a*) = {x1x2…x n| n e xiL(a),1  i  n} =
L(a)0  L(a)1  L(a)2  …= L(a)*
•
• Note que Padrões são cadeias de símbolos
sobre o alfabeto:
{ a | a   }  {e, f , #, @, +, , ~, *, (, )}
EXEMPLOS

•
•
* = L(@) = L(#*)
Conjuntos com um único símbolo: se x  *
, então, x por se só é um padrão e casa
somente com a cadeia x, i.e , {x} = L(x)
Conjuntos finitos: se x1 , … , xm  * ,
então
{x1, x2 , …, xm } = L(x1 + x2 + … + xm )
•
•

•
cadeias contendo pelo menos 3
ocorrências de a:
@a@a@a@
cadeias contendo um a seguido mais tarde
por um b, isto é cadeias da forma xaybz
para algum x, y, z
@a@b@
\{a}
#  (~a)
cadeias sem a ocorrência da letra a (#
 (~a) ) *
Algumas Questões Importantes
Quão difícil é determinar se uma dada
cadeia casa um determinado padrão?
(Existem algoritmos muitos eficientes,
veremos alguns deles. Esta é uma questão
prática.
• Todos os conjuntos são representados por
algum padrão?
(Não! Veremos, por exemplo, que o conjunto
{an bn | n  0} não é representado por
nenhum padrão.)
•
•
Quais operadores são redundantes?
e pois é equivalente a ~(#@) e a f*
@ pois é equivalente a #*
# se  = a1 , a2 , … , an então # é
equivalente a a1 + a2 + … + an .
 a  b é equivalente a ~(~a + ~ b)
•
Todos os padrões são equivalentes a um
padrão usando somente o padrão básico a
para a   , f e os operadores ~,+ , * e •.
Padrões usando somente estes símbolos
são chamados expressões regulares.
Evitando Parêntesis
+ e . São associativas, i. e.
L(a+(b+g)) = L((a+b)+g)
L(a(bg)) = L((ab)g) , e podemos escrever
a+b+g
abg
Precedência:
*
•
Menor
+
Equivalência de Padrões,
Expressões Regulares e Autômatos
Finitos
Teorema:
Seja A  *. As três afirmações abaixo são
equivalentes:
(i) A é regular; i.e., A = L(M) para algum
autômato finito M.
(ii) A = L(a ) para algum padrão a
(iii) A = L(a ) para alguma expressão
regular a .
Prova:
(iii)  (ii)
• A implicação (iii)  (ii) é trivial, uma vez
que toda expressão regular é um padrão por
definição.
(ii)  (i)
O coração desta prova envolve mostrar que
outros conjuntos básicos
(correspondendo aos padrões básicos)
são regulares, e que conjuntos são
fechados sobre operações de fechamento
correspondendo aos operadores usados
para construir padrões.
Note que:
- o conjunto unitário { a } é regular, a  
- o conjunto unitário {} é regular
- o conjunto vazio f é regular, uma vez que
cada um destes conjuntos é um conjunto
aceito por algum autômato.
q0
a
(1)
q1
q0
q0
(2)
Mostramos previamente que os conjuntos
regulares são fechados sobre o conjunto de
operações , , ~ , *, e, ·, i.e. , se A e B são
conjuntos regulares então A  B, A  B,
~A = *\ A, AB e A* são regulares.
Seja a um dado padrão. Queremos mostrar
que L(a) é um conjunto regular. Procedemos
por indução na estrutura de a.
O padrão é de uma das seguintes
formas:
(i) a, para algum a  (vi) b+g
(ii) 
(vii) bg
(iii) f(viii) bg
(iv) #
(ix) ~b
(v) @
(x) b*
São cinco casos base (i) - (v) correspondendo
aos padrões atômicos e cinco casos de
indução correspondendo aos padrões
compostos.
•Para (i) - (iii) temos L(a) = {a} para a ,
L(e L(f) = f estes são conjuntos
regulares.
•Para (iv) e (v), argumentamos antes que os
operadores # e @ são redundantes logo
podemos desconsiderar estes casos.
• Para (vi), lembre que L(b+g) = L(b)L(g) pela
definição do operador +. Pela hipótese da
indução, L(b) e L(g) são regulares. Como
conjuntos regulares são fechados sobre a
união, L(b+g) = L(b)  L(g) é regular.
• Para os casos (vii) - (x) use argumentos
similares aos usados em (vii).
convertendo autômatos em
expressões regulares (I)  (iii)
Dado um subconjunto de estados T de um
AFND M e estados u e v, construamos a
expressão regular:
aTuv
representando o conjunto de todas as
cadeias x tal que existe um caminho de u
para v em M rotulado x (isto é , d*(u, x) = v)
e todos os estados no caminho, com a
possível exceção de u e v estarem em T.
As expressões são construídas por indução
no tamanho de T.
Base T = f
Seja a1, … , ak todos os símbolos em  tal que
d (u, ai) = v.
afuv = a1 + … + ak
se u  v
a1 + … + ak +  se u = v
Indução
Tf
Escolha um elemento qualquer q  T
aTuv = auvT-{q} + auqT-{q} (aqqT-{q} )* aqvT-{q}
Note que qualquer caminho de u para v com
todos os estados intermediários em T ou :
(i) nunca visita q :
auvT-{q}
ou
(ii) visita q uma primeira vez: auqT-{q}
Seguido por um número finito (≥ zero) de
laços de q para q sem visitar q no meio
tempo e ficando em q :
(aqqT-{q} )*
Seguido por um caminho de q para v
deixando q pela última vez
aqvT-{q}
A expressão:
aQsf1 + aQsf2 + … + aQsfk
representa o conjunto de cadeias aceitas por
M, onde
Q é o conjto de todos os estados de M,
s é o estado inicial e
{ f1 , … , fk } é o conjunto de estados finais.
Ex: Converta o autômato em uma expressão
regular equivalente .
1
0
>
q
p
1
0
0
r
T={p,q,r}
app{p,q,r}
Remova q
app{p,q,r}
app{p,r}
=
T- {q}
app{p,r} + apq {p,r}(aqq{p,r})* aqp{p,r}
= 0*
apq{p,r} = 0*1
aqq{p,r} = e + 01 + 000*1
aqp{p,r} = 000*
app{p,q,r} = 0* + 0*1 (e + 01 + 000*1 )*000*
Identificando Linguagens
Não Regulares
• Linguagens regulares podem ser finitas;
• Uma linguagem é regular sss, em
processando qualquer cadeia, a
informação a ser armazenada em
qualquer estágio é estritamente limitada.
• Exemplo: A linguagem L={ an bn|n0} não
é regular.
• Suponha que L é regular. Então existe
um AFD M=(Q, {a,b},S,q0,F) que a
reconhe-ce. Seja k o número de estados
de M. Consideremos o funcionamento de
M na entrada anbn, onde n k
aaaaaaaaaabbbbbbbbbb
n
n
q0
r
• Como nk, deve existir algum estado p
tal que M está em p mais de uma vez
enquanto percorrendo a parte inicial
da seqüência de a’s (princípio da casa
dos pombos).
• Quebre anbn em 3 pedaços u, v, w
onde v é a cadeia de a’s percorrida
entre duas ocorrências de p.
aaaaaa
q0
u
aaaa bbbbbbbbbb
p
v
p
w
r
• Seja j=|v|>0 (j=4, no exemplo)
d* (q0,u) = p
d* (p,v) = p
d* (p,w) = r  F
• Logo podemos remover v o que
resultaria numa cadeia ser
erroneamente aceita:
d*(q0,uw)
= d*(d*(q0,u),w)
= d*(p,w)
=rF
aaaaaa
q0
u
bbbbbbbbbb
p
w
r
Lema do Bombeamento
(Pumping Lemma)
TEOREMA: Seja L uma linguagem regular.
Então existe um inteiro positivo m, tal
que w  L com |w| m pode ser
decomposta como w= xyz com |xz|m e
|y|1 tal que wi=xyiz está também em L
para todo i = 0,1,2, ...
Prova
• Sejam q0, q1,…, qn os estados do AFD que
reconhece L. Agora tome uma cadeia w 
L tal que |w|=km=n+1.
• Seja q0,qi,qj, … ,qf o conjunto de estados
do autômato no reconhe-cimento de w.
Como esta cadeia tem no mínimo n+1
entradas, pelo menos um estado deve ser
repetido, e tal repetição não deve
começar após o n-ésimo movimento.
• Portanto, a sequência deve ter a
seguinte forma
q0,qi,qj, … ,qr, … ,qr, …, qf
• indicando que devem existir subcadeias
x, y, z de w tal que
d*(q0,x)=qr, d*(qr,y)=qr, d*(qr, z)=qf com
|xz|  n+1 = m e |y|1.
• Donde segue imediatamente que
d*(q0,xz)=qf, d*(q0, xy2z)=qf, d*(q0,xy3z)=qf
...
q.e.d
Gramáticas
• Gramáticauma ferramenta comum e
poderosa para definir linguagens.
• Definição: Uma gramática G é uma
quádrupla G=(V, T, S, P) onde:
• V é um conjto finito de variáveis ou símbolos
não-terminais;
• T é um conjunto finito de símbolos terminais;
• S  V é um símbolo especial chamado de
símbolo inicial ou variável de início;
• P é um conjunto finito de produções
• As regras de produção são da forma xy,
onde x é um elemento de (VT)+ e y está
em (VT)*.
• As produções são aplicadas como segue:
• dada uma cadeia w da forma w=uxv, dizemos
que a produção é aplicável a esta cadeia e
podemos usá-la para trocar x por y, obtendo
assim uma nova cadeia z=uyv
• Isto é escrito por wz (w deriva z ou z é
derivada de w ou z deriva de w).
• Se w1w2...wn, dizemos que w1
deriva wn e escrevemos w1*wn
• * indica que foi tomado um número nãoespecificado de etapas (inclu-indo zero)
para derivar wn de w1. Logo w*w
sempre se dá.
• Para indicar que pelo menos uma
produção foi aplicada, escreve-mos
w+v
• Aplicando as regras de produção em
ordens diferentes, uma gramática
pode gerar muitas cadeias. O
conjunto de todas tais cadeias é a
linguagem definida ou gerada pela
gramática.
Linguagem Gerada
• Definição: Seja G = (V, T, S, P) uma
gramática. Então o conjun-to L(G) = {wT*
| S*w} é a linguagem gerada por G.
• Se w  L (G), então a sequência
Sw1w2 … wnw é uma derivação
da sentença (ou palavra) w.
Exemplo
• G = <{S}, {a,b}, S, P> onde P é dado por
SaSb e Se
• Então SaSb  aaSbb  aabb
• Logo podemos escrever S*aabb
• Uma gramática define completamen-te
L(G), porém pode não ser fácil obter uma
descrição explícita da linguagem a partir
da gramática.
• Neste exemplo, no entanto, não é difícil
conjecturar que L(G)={anbn|n0}
Gramáticas Regulares
• Uma gramática G = <V, T,S,P> diz-se
linear à direita se todas as
produções são da forma
A  xB ou Ax
onde A, B  V, e x  T*.
• e linear à esquerda se todas as
produções são da forma
AxB Ax
• Uma gramática regular é uma que é ou
linear à direita ou linear à esquerda.
• Observe que numa gramática regular no
máximo aparece uma variável no lado
direito de qualquer produção. Além
disso, essa variável está mais à
esquerda ou mais a direita de qualquer
produção.
Exemplos
• G1 = ({s},{a,b},S,P1), P1: SabS|a é linear
à direita.
• SabS  ababS  ababa
• L (G1) é a linguagem L((ab)*a)
• G2 = ({S,S1,S2},{a,b},S,P2), com produções
SS1ab, S1S1 ab|S2, S2a é linear à
esquerda.
• S S1abS1ababS2ababaabab
• L(G2) é a linguagem L(a(ab)*)
Cuidado!
A gramática
G=({S,A,B},{a,b},S,P)
com produções
SA
não é regular!
AaB|e
BAb
Gramáticas Lineares À
Direita Geram Linguagens
Regulares
• Construir um AFND que simula as
derivações de uma gramática linear à
direita.
Ab…cDAb…cdE por DdE
• O AFND vai do estado D para o estado E
quando o símbolo d for encontrado.
Teorema. Seja G = (V, T, S, P) uma
gramática linear à direita. Então L(G)
é uma linguagem regular.
Prova. Assumir V={V0,V1,…,Vp}, com
S=V0 e que temos produ-ções da
forma
V0v1Vi, Viv2Vj, …, ou Vnvl, …
• Se w é uma cadeia em L(G), então
por causa das formas das produções
em G, a derivação deve ter a forma
da equação acima.
V0 v1Vi
 v1v2Vj
* v1v2… vk Vn
 v1v2… vk ve = w
• O autômato a ser construído repro-duzirá
a derivação, consumindo cada um desses
v’s.
• O estado inicial do autômato será rotulado V0, e para cada Vi existirá um
estado não final rotulado Vi.
• Para cada Via1a2…amVj definire-mos d
tal que d*(Vi,a1a2…am)=Vj
• Para cada Via1a2…am , d*(Vi,a1a2…am)=Vf,
onde Vf é um estado final. Os estados
intermedi-ários não são de interesse e
podem ser dados rótulos arbitrários.
a1
a2
vi
...
am
vj
representa Via1a2…amVj
a1
a2
vi
representa Via1a2…am
…
am
vf
• Suponha agora que w  L (G). No AFND
existe uma aresta de V0 a Vi rotulada v1,
de Vi a Vj rotulada v2, etc., tal que Vf 
d*(V0, w), e w é aceita por M.
• Inversamente, suponha que w é aceita
por M. Para aceitar w o autômato tem
de passar pela sequência de estados V0,
Vi,…,Vf usando caminhos rotulados
v1,v2,…,vl
• Portanto, w deve ter a forma
w=v1v2…vkvl e a derivação
V0v1Viv1v2Vj*v1v2…vkVk
 v1v2…vkvl
é possível. Logo W está em L(G), e
assim o teorema está provado.
Exemplo
• Construir um autômato que aceita a
linguagem gerada pela gramática
V0aV1
V1abV0 |b
• começamos do grafo de transição com
vértices V0, V1 e Vf.
• A primeira regra de produção cria uma
aresta rotulada a entre V0 e V1. Para
segunda regra, precisamos introduzir um
vértice adicional tal que existe um
caminho rotulado ab entre V1 e V0.
• Finalmente, precisamos adicionar
uma aresta rotulada b entre V1 e Vf
a
v0
b
v1
b
vf
a
v2
• A linguagem gerada pela gramática e
reconhecida pelo autômato é a
linguagem regular L ((aab)*ab)
Gramáticas Lineares À Direita
Para Linguagens Regulares
• Começamos agora do AFD para a
linguagem e invertemos a
construção do teorema anterior
• Os estados do AFD tornam-se as
variáveis da gramática, e
• Os símbolos que causam as
transições tornam-se os terminais
nas produções
• Teorema: Se L é uma linguagem regular
sobre o alfabeto , então existe uma
gramática linear à direita G = (V,,S,P) tal
que L = L(G).
• Prova: Seja M = (Q,,d,q0, F) um AFD que
aceita L. Assumiremos que Q = {q0,q1,…,
qn) e  = {a1, a2,…am}.
• Vamos construir uma gramática linear à
direita G = (V, , S, P) com V = {q0, q1,…,qn}
e S = q0.
• Para cada transição d (qi, aj) = qk de M,
colocamos em P a produção qiajqk.
• Além disso, se qk está em F,
acrescentamos a P a produção q.
• Primeiro mostramos que G defini-da
dessa maneira pode gerar toda cadeia
em L. Considere w  L da forma
w = aiaj…akal.
• Para M aceitar essa cadeia ele deve se
movimentar via
d (q0, ai) = qp,
d (qp, aj) = qr,
...
d (qs, ak) = qt,
d (qt, al) = qf  F
• Por construção, a gramática terá
uma produção para cada um desses
d’s. Portanto, podemos fazer a
derivação
q0aiqpaiajqr*aiaj…akqt
 aiaj…akalqfaiaj…akal
com a gramática G, e w  L(G).
• Inversamente, se w  L(G), então sua
derivação deve ter a forma da equação
acima, mas isto implica que
d (q0, ai, aj…akal) = qf,
completando a prova.
q.e.d.
Equivalência Entre
Linguagens Regulares E
Gramáticas Regulares
• Os resultados anteriores estabele-cem a
conexão entre linguagens regulares e
gramáticas lineares à direita.
• Podemos fazer uma conexão análo-ga
entre linguagens regulares e gramáticas
lineares à esquerda, mostrando assim, a
equivalência de gramáticas e linguagens
regulares.
Teorema.
Uma linguagem é regular se e
somente se existe uma gramáti-ca
regular G tal que L = L(G).
Álgebra de Kleene e
Expressões Regulares
• α  β significa que L(α)=L(β).
α+(β+γ)  (α+β)+γ
α+β  β+α
α+  α
α+α  α
α(βγ)  (αβ)γ
αε  εα  α
α  α  
α(β+γ)  αβ+αγ
(α+β)γ  αγ+βγ
ε+αα*  ε+α*α  α*
β+αγ ≤ γ  α*β ≤ γ
β+γα ≤ γ  βα* ≤ γ
algumas consequências úteis:
(αβ)*α  α(βα)*
(α*β)*α*  (α+β)*
α*(βα*)*  (α+β)*
(ε+α)*  α*
• a expressão abaixo:
app{p,q,r} = 0* + 0*1 (e + 01 + 000*1 )*000*
pode ser simplificada uma vez que:
e + 01 + 000*1  e + 0(e + 00*)1
 e + 00*1
• logo:
app{p,q,r} = 0* + 0*1 (e + 00*1)*000*
Usando o Lema do
Bombeamento
• Ilustaremos o uso do lema para mostrar
que
A={anbm|nm}
não é regular.
• Se A é regular, sejam w=akbk e m como no
lema com decompo-sição x, y e z
• possíveis decomposições:
• y seria composta só de a’s;
• y seria composta só de b’s;
• y não pode ser composta de a’s e b’s.
• no primeiro caso w0A;
• no segundo, w2A
• C={an! | n0} não é regular!
• Se C é regular, sejam w=ak! e m como
no lema com decomposi-ção x, y e z e
tamanhos j, n e l.
• Pelo lema para cada i existe p tal que
|wi|=p!. Então seja i=(k+1)!+1.
p! = |wi| = j+in+l = k!+(i-1)n =
= k!+(k+1)!n = k!(1+n(k+1))
• dividindo os extremos por k! :
p(p-1)(p-2)…(k+2)(k+1)=1+n(k+1)
o que é um absurdo!!
Um Truque
• algumas vezes ajuda utilizar o truque de
se tomar interseção na prova de que
algum conjunto não é regular.
• se encontrarmos L regular com A∩L não
regular (conhecido) então A não é regular
Exemplos
• D={x є {a,b}*| |x|a=|x|b} não é regular pois
D∩L(a*b*)={anbn|n≥0}
• Se A={anbm|n ≥ m} fosse regular tam-bém o
seria
rev A = {bman |n ≥ m} (exercício).
• Trocando-se a’s por b’s obtemos A’={ambn|n ≥
m} que seria também regular.
• Mais aí a interseção A∩A’={anbn|n≥0} seria
regular, o que é um absurdo!!
Exercícios
1.Construir um AFD que reconhe-ce a
linguagem gerada pela gra-mática
SabA; AbaB; BaA | bb
2.Construir uma gramática linear à
direita para a linguagem
L ( (aab* abab)*)
Exercícios
3. Dê expressões regulares para cada um
dos seguintes subconjuntos de {a,b}*:
(a) {x|x contém um número
(b) {x|x contém um número
(c) {x|x contém um número
número ímpar de b’s}
(d) {x|x contém um número
número ímpar de b’s}
par de a’s}
ímpar de b’s}
par de a’s ou um
par de a’s e um
Exercícios
4. Dê AFD aceitando o conjunto de cadeias
casando com as seguintes expressões
regulares:
(a) (000* + 111*)*
(b) (01 +10) (01 +10) (01 +10)
(c) (0 + 1 (01* 0)* 1)*
Exercícios
5. Mostre que os conjuntos abaixo não são
regulares:
(a) {anbm | n=2m}
(b) {x{a, b, c}* |x é palindrome, I.e., x=rev(x)}
(c) {x{a, b,c}* | o tamanho de x é um quadrado}
(d) O conjunto PAREN de cadeias de parentesis
balanceada. Por exemplo, a cadeia ( ( ( ) ( ) ) ( ) )
está em PAREN mas a cadeia ) ( ( ) não está.
Uma variação do Lema do
Bombeamento
• Reformularemos o enunciado do Lema de
maneira a torná-lo mais facilmente
aplicado em algumas situações.
• A reformulação permitirá o uso de um
método de prova baseado num jogo
contra o diabo
Variação do Lema
Teorema. Seja A um conjunto regular.
Então a seguinte propriedade se dá
sobre A:
(P) Existe k≥0 tal que para quais_quer
cadeias x,y,z com xyzA e |y|≥k,
existem cadeias u,v,w tais que y=uvw,
v≠ε, e para todo i≥0, a cadeia
xuyivwzA
Negando (P)
Teorema. Seja A um conjunto de cadeias e
suponha que:
(~P) Para todo k≥0 existem cadeias x,y,z
com xyzA e |y|≥k, e para todas cadeias
u,v,w tais que y=uvw, v≠ε, e existe i≥0,
tal que cadeia xuyivwzA.
Então A não é regular.
Jogando contra o diabo
O diabo quer mostrar que A é regular e
voçê que não!
• Ele então pega k.
• Você vai escolhe xyzA e |y|≥k.
• Daí ele pega u,v,w tais que y=uvw, v≠ε,
• Você mostra o i≥0, com xuyivwzA
Exemplo de Uso
• No exercício 5 último foi pedido para
mostrar que {x{a, b, c}* |x é palíndrome,
i.e., x=rev(x)} não é regular.
• Dado k do diabo basta escolher x= ε, y=ak e
z=bak. Qualquer escolha u,v,w do diabo
com, digamos |v|=m>0, basta escolher i=0 e
xuv0wz=xuwz=ak_mbakA
Minimização de Estados
remover estados inalcançáveis ou
colapsando estados equivalentes.
a
b
a
a,b
a,b
b
a
a
b
a
a
b
b
b
a
a
b
Um autômato mínimo
b
a
b
a
b
a
a,b
Resumindo ...
• dado M = (Q, , d, s, F):
• Livrar_se dos estados inalcançáveis, i.e. dos
estados q tais que não existe cadeia x* tal
que d*(s,x)=q.
• Colapse estados equivalentes
Mais exemplos
a
a,b
a,b
a,b
a,b
a,b
b
a,b
a
a
a,b
b
a,b
a,b
b
a,b
a,b
a,b
b
a,b
a
Ainda mais exemplos
a
a
a,b
b
a,b
a,b
b
a,b
a,b
b
a,b
a
A Construção do Quociente
• Como saber com segurança que dois
estados podem ser colapsados
• como fazer o colapso formalmente?
• como determinar se mais colapsos
podem ser feitos?
• nunca colapsaremos um estado que
rejeita com um que aceita:
p=d*(s,x)F e q=d*(s,y)F
colapsar p com q aceitar y ou rejeitar
x.
• o colapso de p e q implica no
colapso de d(p,a) com d(q,a)
A equivalência
• Logo, p e q não podem ser
colapsados se
d*(p,x)F e d*(q,x)F
• Então definamos uma relação de
equivalência ≈ sobre Q por:
p≈q
se, e somente se
x*(d*(p,x)Fd*(q,x)F)
• não é difícil mostrar que de fato ≈ é
uma relação de equivalência.
• [p]:={q|q≈p}
• p≈q sss [p]=[q]
O Autômato Quociente
• Dado M, definamos
M/≈ = (Q’,, d’,s’, F’)
onde:
Q’={[p] | pQ}
d’([p],a)=[d(p,a)]
s’=[s]
F’={[p] | pF}
Resultados Úteis
Lema 1. Se p≈q, então d(p,a)≈d(q,a).
Equivalentemente, se [p]=[q] então
[d(p,a)]=[d(q,a)].
Lema2. pF sss [p]F’.
Lema3. d’*([p],x)=[d*(p,x)]
Teorema. L(M/≈)=L(M)
Prova. Para x  *,
x  L(M/≈) sss d’*(s’,x)  F’ def. de aceita
sss d’*([s],x)  F’ def. de s’
sss [d*(s,x)]  F’ lema 3
sss d*(s,x)  F lema 2
sss x  L(M) def. de aceita
qed
M/≈ não pode ser mais
colapsado
• Defina
[p]~[q]
sss
x*(d’*([p],x)F’d’*([q],x)F’)
[p]~[q]
x*(d’*([p],x)F’d’*([q],x)F’)
x*([d*(p,x)]F’[d*(q,x)]F’) lema 3
x*(d*(p,x)Fd*(q,x)F’) lema 2
 p≈q
[p]=[q]
Algorítmo de Minimização
1. Escreva uma tabela dos pares {p,q},
inicialmente desmarcados
2. Marque {p,q} se pF e qF ou vice_versa.
3. Repita até que não poder mais: se existe
um par desmarcado {p,q} tal que
{d(p,a),d(q,a)} é marcado para algum a,
então marque {p,q}.
4. Quando acabar 3, p≈q sss {p,q} é
desmarcado.
Exemplo
a
3
1
a,b
b
5
0
b
b
a,b
2
a,b
4
a,b
a,b
a,b
a,b
1
2
3
4
5
_■
_■
_
■
_
■
_■
0
_
■
_ _■
■
_ _■ _
_ _ ■_ ■
_
■ ■
1 2 3 4
Corretude do Algorítmo
Q={{p,q} | p,qQ}
={{p,q} | p≠q}  {{p} | pQ}
logo existem
2
n( )+n=(n +n)/2.
2
seja agora Δ: Q → Q
Δ({p,q},a)={d(p,a),d(q,a)}
e F ={{p,q} | pF, qF }
X:= F
repeat
X’:=X;
X:=X 
{{p,q}|a. Δ({p,q},a)X}
until X=X’
• X é o conjunto dos
marcados
Corretude do Algorítmo
X = {{p,q} | x*. Δ*({p,q},x}F}
= {{p,q} | x*. d*(p,x)F,d*(q,x)F }
= {{p,q} |(x*.(d*(p,x)Fd*(q,x)F ))}
= {{p,q} |
(p≈q)
Linguagens Livre de Contexto
<stmt>::=<if-stmt>|<while-stmt>|
<begin-stmt>|<assg-stmt>
<if-stmt>::=if <bool-expr> then <stmt>
else <stmt>
<while-stmt>::=while <bool-expr>
do <stmt>
<begin-stmt>::=begin <stmt-list> end
<stmt-list>::=<stmt>;<stmt-list>|<stmt>
<assg_stmt>::=<var>:=<arith-expr>
<bool-expr>::=
<arith-expr><comp-op><arith-expr>
<comp.-op>::=<|>|≤|≥|≠|=|
<arith-expr>::=<var>|<const>|
(<arith-expr><arith-op><arith-expr>)
<arith-op>::=+ | - | *| /
<const>::=0|1|2|3|4|5|6|7|8|9
<var>::=a|b|c|…|x|y|z
BNF (Backus-Naur form)dando a definição
formal de uma linguagem de
“programação”.
Mais Exemplos
• L = {anbn|n0} é livre de contexto.
• Se em L substituirmos ‘a’ por ‘(‘ e ‘b’ por
‘)’, cadeias de parênte-ses tais como ( ( )
) e ( ( ( ) ) ) estarão em L.
• L descreve uma estrutura aninhada
comum em linguagens de progra-mação.
Gramáticas Livre De
Contexto
•As produções numa gramática regu-lar
são restritas de duas formas:
• o lado esquerdo deve conter uma única
variável,
• enquanto o lado direito tem uma forma
especial.
•Para criar uma gramática “mais
poderosa”, devemos relaxar algumas
dessas condições .
• Mantemos a restrição sobre o lado
esquerdo, mas permitimos qualquer
coisa no lado direito.
Definição: Uma gramática G=<V,T,S,P>
é livre de contexto se todas as
produções em P tem a forma Ax,
onde AV e x(VT)*.
•A linguagem L é livre de contexto sss
existe uma gramática livre de contexto
G tal que L = L(G).
Obs: Toda linguagem regular é livre de
contexto.
Exemplos
• G=<{S},{a,b},S,P>, com produ-ções
SaSa; SbSb, Se
• Uma derivação típica nessa gramática é
SaSaaaSaaaabSbaaaaabbaa
• Isto torna claro que L(G)={WWR|W{a, b}*}
Mais Exemplos
• A gramática
G=<{S, A, B}, {a, b}, S, P>,
onde P é
SabB; AaaBb; BbbAa; Ae
• L(G)={ab (bbaa)n bba (ba)n |n0}
Derivação Mais à Esquerda e
Mais à Direita
G=<{A,B,S},{a,b},S,P> com
produções:
1. SAB;
2. AaaA;
3. Ae;
4. BBb;
5. Be.
L(G)={a2nbm|n0, m0}
S1AB2aaAB3aaB4a
aBb5aab
S1AB4ABb
2aaABb5aaAb
3aab
Definição:
• Uma derivação diz-se mais à
esquerda se em cada etapa a
variável mais a esquerda é trocada
na forma sentencial.
• Se em cada etapa a variável mais a
direita é trocada, dizemos que a
derivação é mais à direita.
Exemplos
Considere a gramática com produ-ções
SaAB, AbBb, BA|e
• uma derivação mais à esquerda da
cadeia abbbb:
SaABabBbBabAbBabbBbbBabbb
Babbbb
• uma derivação mais à direita:
SaABaAabBbabAbabbBbbabbb
b.
Árvores de Derivação
•Mostra derivações independente da ordem
em que as produções são usadas.
•Uma árvore de derivação é uma árvore
ordenada onde:
• os nodos são rotulados com os lados esquerdos
das produções e
• o filho de cada nodo representa seus
correspondentes lados direitos.
Exemplo
Aa b A B c
A
a
b
A
B
c
Definição
Seja G=<V, T, S, P> uma gramática livre de
contexto. Uma árvore ordenada é uma
árvore de derivação para G se e
somente se ela tem as seguintes
propriedades:
1. A raiz tem rótulo S
2. Toda folha tem rótulo de T{e}
3. Todo vértice interior tem um rótulo de
V.
4. Se um vértice tem rótulo A  V, e seus
filhos são rotulados(da es-querda para
direita) a1, a2, …,an, então P deve conter
uma produção da forma Aa1a2…an
5. Uma folha rotulada e o seu pai não
tem nenhum filho além dàquele rótulado
e.
árvore de derivação parcial:
• Uma árvore que tem as proprieda-des 3,
4 e 5 mas não necessaria-mente 1 e
• a propriedade 2 é trocada por:
2a.Toda folha tem rótulo em VT{e}
cadeia gerada
A cadeia de símbolos obtida lendo-se,
da esquerda para à direita, omitindo
qualquer e encontrado, diz-se gerada
pela árvore.
Exemplo: Considere a gramática G,
com produções
SaAB
AbBb
BA |
e
Exemplo (a)
(a)
• A árvore (a) é uma ár-vore
de derivação par-cial para
G.
• A cadeia abBbB, gera-da
pela árvore, é uma forma
sentencial de G.
S
a
b
A
B
B
b
Exemplo (b)
• a árvore (b) é uma árvore de derivação.
• A cadeia gerada, abbbb é uma sentença de
L(G).
(b)
S
a
B
A
b
B

A
b
b
B

b
Relação entre Formas
Sentenciais e Árvores de
Derivações
•Árvores de derivação dão uma descrição explícita e compreensível de
derivações.
•Assim como grafo de transições para
autômatos finitos, elas são úteis nos
argumentos.
Teorema
Seja G=<V, T,S, P> uma gramática livre de
contexto.
Então pra todo wL(G) existe uma árvore
de derivação G cuja cadeia gerada é w.
Inversamente a cadeia gerada por qualquer árvore de derivação está em G.
Além disso, se tG é qualquer árvore de
derivação parcial para G cuja raiz é
rotulada S, então tG gera uma forma
sentencial de G.
Prova
• Primeiramente, mostraremos que
para toda forma sentencial de G
existe uma árvore de derivação
parcial.
• Faremos isso por indução no número
de etapas da derivação.
Prova (cont.): base
Como base, observemos que a afir-mação
é verdadeira pra toda forma sentencial
derivada em uma etapa. Como Su
implica que existe uma produção Su,
isto segue imediata-mente da definição
da árvore de derivação.
Prova(cont.): passo
Suponhamos que para toda forma
sentencial derivável em n etapas,
existem uma árvore de derivação parcial
correspondente.
Prova(cont.): passo
Agora qualquer w derivável em n+1 etapas
deve ser tal que
S*x A y, x, y  (V U T)*, A V
em n etapas, e
x A yx a1, a2…amy = w,
ai  VT.
• mas por hipótese de indução existe uma
árvore de derivação parcial que gera x A
y.
• como G deve ter produção Aa1a2…am,
expandindo as folhas rotuladas A,
obtemos uma árvore de derivação parcial
que gera w.
• Logo, por indução, o resultado é
verdadeiro para toda forma senten-cial.
• Usando um argumento análogo,
podemos mostrar que toda árvore de
derivação parcial representa alguma
forma sentencial.
• Uma árvore de derivação é uma árvore
de derivação parcial cujas folhas são
terminais.
• Logo toda sentença em L(G) é gerada
por alguma árvore de deri-vação de G e
toda árvore de derivação gerada está
em L(G).
q.e.d
•Árvores de derivação mostram quais
produções são usadas para se obter uma
sentença, mas não dá a ordem de suas
aplicações.
•Árvores de derivações são capazes de
representar qualquer derivação, refletindo
o fato de que esta ordem é irrelevante,
uma observação que nos permite fechar o
buraco na discussão anterior.
• Por definição, qualquer wL(G) tem uma
derivação mais a esquerda e uma mais a
direita.
• dada uma árvore de derivação, po-demos
sempre obter uma derivação mais a
esquerda pensando na árvore como tendo
sido construída de tal modo que a variável
mais a esquerda foi sempre expandida
primeiro.
• Todo w  L(G) tem pelo menosuma
derivação mais a esquerda e uma mais a
direita.
Análise
•Dada uma cadeia de terminais w,
queremos saber se wL(G) ou não.
•Se for o caso, poderemos querer achar uma
derivação de w.
•Um algoritmo que pode nos dizer se wL(G)
é um algoritmo de pertinência
•o termo análise descreve o modo de achar
uma sequência de produções pela qual é
derivada wL(G).
• análise óbvia se w está L(G):
• construir todas as possíveis (e.g. as mais à
esquerda) derivações e verificar se al-guma
coincide com W.
• análise de pesquisa exaustiva
• Problemas:
• não é eficiente;
• é possível que ele nunca termine wL(G).
Por cause de produções da forma
AB e Ae
Ambigüidade
•Uma gramática livre de contexto G é
ambígua se existe wL(G) com no mí-nimo
duas árvores de derivação.
•ambiguidade  a existência de ≥2
derivações à esquerda e à direita.
Exemplo: A gramática com produções SaSb
| SS | e é ambígua.
• aabb tem duas árvores de derivação:
S
S
a
S
b
a
S
b
e
S
S
a
e
a
S
S
e
b
b
Soluções
•Re-escrever a gramática tal que exista
somente uma análise possível;
•Associar regras de precedência
(como feito em LP com os + e *)
• Esta solução está completamente fora da
gramática.
•existem exemplos onde é impossível
remover a ambiguidade da gramática.
Abigüidade Inerente
não-ambígua:
• existe uma gramática para L que é nãoambígua;
inerentemente ambígua
.se toda gramática para L é ambígua.
e.g.:
L={anbncm|n,m>0}{anbmcm|n,m>0}
Formas Normais
•A definição de uma GLC não impõe
qualquer restrição no lado direito de uma
produção.
•Em muitas situações (aplicações) é
desejável colocar restrições.
•Estudaremos métodos de transformar uma
GLC arbitrária numa equivalente que
satisfaz certas restrições sobre sua forma.
Forma Normal de Chomsky
Uma gramática livre de contexto está na
forma normal de Chomsky se todas as
produções são da forma
ABC ou Aa
onde A, B, C  V e a  T.
Forma Normal de Greibach
Uma gramática livre de contexto está na
forma normal de Greibach se todas as
produções tem a forma
Aa B1 B2…Bk
para k0, com A, B1, BkV e aT.
Teorema de Normalização
Teorema:
Para toda GLC G, existe uma GLC G’ na
forma normal de Chomsky e uma GLC G’’
na forma normal de Greibach tal que
L(G’’)=L(G’)=L(G) - {e }
Remoção de Produções
Unitárias AB e e-Produções
Lema:
Para qualquer GLC G=(N, , P, S), exis-te
uma GLC G’ sem e-produção e sem
produção unitária tq L(G’)=L(G) - {e}.
Prova
Seja P^ o menor conjunto de produ-ções
contendo P e fechado sobre as duas
regras:
(a)Se AaBb  P^ e Be  P^, então
Aab  P^
(b)Se AB  P^ e Bg  P^, então
Ag  P^
•Podemos construir P^ indutivamen-te de
P adicionando produções para satisfazer
(a) e (b).
•Seja G^ a gramática G^=(N, , P^, S)
como P P^:
• L(G)  L(G^), obviamente!
• mas L(G)=L (G^), porque cada nova
produção adicionada pode ser simula-da
pela produção que a adicionou.
Agora mostramos que para cada
cadeias não nulas x, qualquer
derivação S*G^ x de tamanho mínimo
não usa e-produção nem produção
unitária.
• Seja xe considere a derivação de
tamanho mínimo S*G^ x. Suponha
para a contradição que Ae é usada
em algum ponto da derivação
S*aAb ab *x com a ou b não nulo.
•esta ocorrência de A aparece na
derivação quando uma produção da forma
B gA d é aplicada:
Sm B  gAd n aAb  ab *x para
algum m,n,k0.
•Mas pela regra (a) B g d está tam-bém
em P^, e esta produção poderia ter sido
usada neste ponto dando uma derivação
menor de x:
SmB  gd nab kx
absurdo!
Um argumento similar mostra que
produções unitárias não são usadas em
derivações de tamanho mínimo.
Seja x  e e considere a derivação de
tamanho mínimo S*G^ x. Suponha que
AB é usada em algum mo-mento
S*aAb  aBb *x.
a ocorrência de B desaparece apli-cando a
produção B g mais tarde:
SmaAb aBbn  B   g  kx
• Mas pela regra (b), A g está também
em P^ e esta produção poderia ter
sido usada dando uma derivação
menor para x: SmaAb agbn g kx
• Isto contradiz o tamanho mínimo da
derivação.
Logo as e-produções e produções
unitárias podem ser descartadas!
qed
Transformando para a forma
normal de Chomsky.
SPG só consideraremos gramáticas sem e
- produções e produções unitá-rias:
•Para cada a, introduza um novo não
terminal Aa e a produção Aa a, e troque
todas as ocorrências de a no lado direito
das antigas regras (exceto das regras de
forma B a) por Aa.
•Então todas as produções são de uma
das duas formas
Aa ou AB1B2…Bk, k2
onde os Bi são não terminais.
•O conjunto de cadeias terminais não
muda, somente temos mais um passo(que
antes)para gerar um sím-bolo terminal.
• Para qualquer produção A B1B2. …Bk com
K>2, introduza um novo não terminal C e
troque esta produção por duas
A B1C e C  B2B3 …Bk ..
• Continue fazendo estas trocas até que
todos os lados direitos tenham tamanho no
máximo 2.
Exemplo
Derive a gramática na forma normal de
Chomsky para o conjunto
{anbn | n0} - {e} = {anbn | n 1}.
•pegue gramática para {anbn | n0} :
SaSb|e
•Removendo as e - produções temos:
S aSb | ab
que gera {anbn | n 1}.
• Adicionamos não-terminais A, B e
trocamos as produções para:
S ASB| AB A a B b
• Adicionamos um não-terminal C e
trocamos
B ASB por S AC C SB.
A gramática na forma normal de
Chomsky é
S AB|AC A a B b C  SB
AUTÔMATO A PILHA
fita de entrada
esquerda p/ direita,read only
x1
x2
x3
x4
x5
x6
...
xn
A1
A2
Q
unidade
de controle
A3
push/pop
A4
z
pilha
Definição NPDA
autômato a pilha não-determinís-tico M=<
Q,,,d,q0,,F>
Q
► estados

► alfabeto da fita

► alfabeto da pilha
q0Q
► estado inicial
z
► símbolo de início da pilha
FQ
► estados finais
d
► função de transição
d : Q x ( U {e} ) x   Q x *
se ( (p,a,A),(q,B1B2. …Bk ) )  d isto significa
intuitivamente que quando a máquina
está no estado p lendo o símbolo a (na
fita de entrada) e A (no topo da pilha),ela
tira A da pilha,coloca B1B2. …Bk na pilha
(Bk primeiro e B1 por último),move a
cabeça para a direita uma célula
passando o símbolo a e entra no estado
q.
EXEMPLO: Considere o npda com
Q={q0,q1,q2,q3),={a,b},={0,1}, z=0, F =
{q3} e
d(q0,a,0)={(q1,10),(q3,e)}
d(q0,e ,0) = {(q3,e)}
d(q1,a,1) = {(q1,11)}
d((q1,b,1) = {(q2,e)}
d(q2,b,1) = {(q2,e)}
d(q2,e ,0) = {(q3,e)}
•Não são especificadas transições para
todas as combinações possíveis de
entradas e símbolos da pilha;
•Uma transição não especificada vai para o
conjunto vazio e representa uma
configuração morta do npda;
•Transições cruciais
• d (q1,a,1) = {(q1,11)} adiciona 1 a pilha quando
é lido um a ;
•
d (q2,b,1) = {(q2,e)} remove 1 quando um b é
encontrado.
• Estas duas etapas contam o número de a’s
e compara este número com o número de
b’s.
• A unidade de controle fica no estado q1 até
ser encontrado o primeiro b e aí entra no
estado q2. Isto assegura que nenhum b
precede o último a.
• Após analisar as transições restantes,
veremos que o npda terminará no estado
final q3 se e somente a cadeia de entrada
está na linguagem
L = {anbn | n 0}  {a}
•A tripla (q,w,u), onde q é o estado da
unidade de controle, w é a parte não lida
da cadeia, e u o conteúdo da pilha (com o
símbolo mais a esquerda indicando o topo
da pilha) é chamada uma descrição
instantânea do autô-mato a pilha.
• Um movimento de uma descrição
instantânea para outra será denotada
pelo símbolo |—
(q1,aw,bx)|—(q2 ,w,yx)
• é possível se e somente se
(q2,y)d(q1,a,b)
• |—*
|—+
|—m
A Linguagem Aceita por um
Autômato a Pilha
•Existem duas definições alternati-vas
para aceitação, por:
pilha vazia ou estado final.
•Para um pda M = <Q,,,d,q0,z,F> a
linguagem L(M) aceita por M por estado
final é
L(M)={w|(q0,w,z) |—* (p,e,)pF e *}
a linguagem L(M) aceita por M por
pilha vazia é
L(M)={w|(q0,w,z) |—* (p,e,e), qQ}
Obs: Quando a aceitação é por pilha
vazia, o conjunto de estados finais é
irrelevante, e neste caso geralmente
defi-nimos o conjunto de estados
finais como o conjunto vazio.
EXEMPLO.
Considere o npda com Q={q}, ={[,]},
 = {,[}, q0=q, z= e
(i) d(q,[,) = (q,[)
(ii) d(q,[,[) = (q,[[)
(iii) d(q,],[) = (q,e)
(iv) d(q,e, ) = (q,e)
•Transições (i) e (ii) dizem que toda vez
que o próximo símbolo de entrada é [,o [
deve ser colocado no topo da pilha.
• Transição (iii) diz que quando o pró-ximo
símbolo de entrada é ] com um [ no topo
da pilha, removemos o [ e não colocamos
mais nada na pilha.
• Transição (iv) ocorre quando alcan-çamos
o fim da cadeia de entrada e queremos
retirar  da pilha e aceitar o padrão.
• Dada a entrada [[[]][]][] a sequência de
configurações do autômato até a
aceitação da cadeia:
(q, [[[]][]][],
 ) conf. Inicial
(q, [[]][]][],
(q,
(q,
(q,
(q,
(q,
(q,
(q,
(q,
(q,
(q,
[ ) (i)
[]][]][], [[ ) (ii)
]][]][], [[[ ) (ii)
][]][], [[ ) (iii)
[]][], [ ) (ii)
]][], [[ ) (ii)
][], [ ) (iii)
[],
 ) (iii)
],
[ ) (i)
e,
e,
 ) (iii)
e ) (iv)
Obs: A transição (iv) poderia ter sido usada
várias vezes anteriormente, por exemplo,
no primeiro passo levaria a seguinte
configuração
(q,[[[]][]][] ,e ) e autômato pararia, com a
pilha vazia mas sem ter lido toda a
entrada!
Autômatos à Pilha E
Linguagens Livre de Contexto
Autômatos à pilha para linguagens livre de
contexto.
•Mostrar que para toda linguagem livre de
contexto existe um npda que a aceita.
•A idéia subjacente é construir um npda que
possa, em algum sentido, efetuar uma
derivação mais a esquer-da de qualquer
cadeia da linguagem.
• Para simplificar assumiremos que a
linguagem é gerada por uma gramática
na forma normal de Greibach.
AaB1B2…Bk, k0
• Construir de G um npda equivalente M
com um único estado que aceita a
linguagem por pilha vazia.
M = ({q},,N,d,q,S, Φ)
q é o único estado e é estado inicial
 , os terminais de G, é o alfabeto de entrada
de M
N , os não-terminais de G, é o alfabeto da
pilha de M
d é a função de transição
S é o símbolo inicial de G, e o símbo-lo inicial
da pilha de M.
Φ conjunto vazio de estados finais de M
•Para cada produção A  aB1B2…Bk em P, d
contém a transição
((q,a,A),(q,B1B2…Bk) )
Exemplo:
•Considere o conjunto de cadeias de parên-teses
balanceadas [ ] e uma gramática G.
•Abaixo temos as regras de produção de G ao lado
da transição correspon-dente pela construção vista
anteriormente:
(i) S  [BS
(ii) S  [B
(iii) S  [SB
(iv) S  [SBS
(v) B  ]
((q,,S),(q,BS))
((q,,S),(q,B))
(q,,S),(q,S B))
(q,,S),(q,SBS))
(q,,B),(q,e))
Considere a entrada x = 
regra | forma sentencial |
S
(iii)
SB
(iv)
 SBSB
(ii)
   BBSB
(v)
   BSB
(v)
    SB
(ii)
     BB
(v)
B
(v)


configuração
(q,      ,S)
(q,     ,SB)
(q,    ,SBSB)
(q,    ,BBSB)
(q,   ,BSB)
(q,  ,SB)
(q, ,BB)
(q, ,B)
(q,e,e)
Lema:Para qualquer z,yΣ*, γГ*, e AN, A
*zγ por uma derivação a esquerda se e
somente se
(q,zy,A) * (q,y, γ).
Teorema: L(M) = L(G).
Prova: x  L(G)
 S * x por uma derivação a esquerda
(definição de L(G) )
 (q,x,s) *(q,e ,e ) (lema)
 x  L(M) definição de L(M).
q.e.d
Gramáticas livre de contexto para autômatos
a pilha.
•A inversa do teorema acima também é
verdadeira.
•A construção é reverter o processo de
construção de L(M) = L(G), de modo que a
gramática simule os movimentos do pda.
•Isto significa que o conteúdo da pilha deve
estar refletido na parte de variá-veis na
forma sentencial, enquanto a entrada
processada é o prefixo termi-nal da forma
sentencial.
• Para simplificar assumamos que o pda
M satisfaz:
1. Tem único estado final qf no qual só
entra sss a pilha estiver vazia.
2. Todas as transições devem ter a
forma d(q,a,A)={C1,C2,…,Cn}, onde:
Ci=(p,e) (a)
ou
Ci=(p,BC) (b)
• Estas restrições não são tão severas
quanto parece. Mostre como, dado um
pda qualquer, obter um satisfazendo 1 e
2 acima.
• Na construção da gramática devemos
ter uma forma sentencial que reflita o
conteúdo da pilha.
• Observe que a configuração de um pda
também envolve um estado que deve ser
lembrado.
• Logo as varáveis da gramática têm que
ter a forma (qiAqj).
• (qiAqj)*w sss o pda apaga (desempilha) A da pilha, indo de qi para qj
enquanto lê a cadeia w.
• se (qj,e)d(qi,a,A) (tipo 2a), então
(qiAqj)a
• se (qj,BC)d(qi,a,A) (tipo 2b), então
(qiAql)a(qjBqk)(qkBql)
• onde qk e ql varrem todo o Q.
• como símbolo inicial faça: (q0zqf)
• Exemplo: seja o pda definido por:
d(q0,a,z)=(q0,Az)
d(q0,a,A)=(q0,A)
d(q0,b,A)=(q1,e)
d(q1,e,z)=(q2,e)
não satisfaz condição 2, mas ...
d(q0,a,A)=(q3,e)
d(q3,e,z)=(q3,Az)
• De d(q0,a,A)=(q3,e), d(q0,b,A)=(q1,e) e
d(q1,e,z)=(q2,e) geramos:
(q0Aq3)  a
(q0Aq1)  b
(q1zq2)  e
De d(q0,a,z)=(q0,Az) geramos:
(q0zqi)a(q0Aq0)(q0zqi)|
a(q0Aq1)(q1zqi)|
a(q0Aq2)(q2zqi)|
a(q0Aq3)(q3zqi)
para i=0,1,2,3
E de d(q3,e,z)=(q3,Az) geramos:
(q3zqi)(q3Aq0)(q0zqi)|
(q3Aq1)(q1zqi)|
(q3Aq2)(q2zqi)|
(q3Aq3)(q3zqi)
para i=0,1,2,3
• o símbolo inicial é (q0zq2).
• Vejamos como se comportam M e G
em aab:
• Em M:
(q0,aab,z) |— (q0,ab,Az)
|— (q3,b,z)
|— (q0,b,Az)
|— (q1,e,z)
|— (q2,e, e)
• em G:
(q0z q2)  a(q0Aq3)(q3zq2)
 aa(q3zq2)  aa(q0Aq1)(q1zq2)
 aab(q1zq2)  aab
• Teorema. Se L=L(M) para algum pda
M. então L é uma linguagem livre de
contexto.
Lema da Bomba
(Pumping Lemma)
para linguagens livre de contexto
• Este lema é útil para mostrar que uma
dada linguagem não é uma linguagem
livre de contexto.
• Seu uso é análogo àquele visto para
linguagens regulares.
• Suponha G na FNC e seja m=2k+1, onde
k=|V|.
• se |w|  m, então uma àrvore de derivação
para w em G tem altura mínima > k
D
S
D
a
w=abg
P
A

g
b

A
v
b=vxy
P’
y
x
S*aDg*aAg*avAyg*avxyg
S*avAyg*avvAvyg *aviAyig
Teorema. Seja L uma linguagem livre de
contexto infinita. Então existe algum
inteiro positivo m tal que para qualquer w
 L com |w|  m ela pode ser decomposta
como
w = uvxyz (1)
com
|vxy|  m (2)
e
|vy|  1
(3)
tal que, para todo i =0,1,2,…:
uvixyiz  L
EXEMPLO:
Mostre que L = {anbncn : n 0} não é livre de
contexto.
SOLUÇÃO: (dos diabos :-)
1. O diabo escolhe m;
2. tomamos a cadeia ambmcm em L.
3. O diabo tem várias escolhas.
3a. Se ele escolhe vxy contendo somente
a’s, então o bombeamento acarreta
obviamente que a cadeia não está em L.
3b. Se ele escolhe uma cadeia contendo
número igual de a’s e b’s então a cadeia
bombeada akbkck com km pode ser
gerada, e não está em L.
De fato, a única maneira do diabo
tentar nos impedir de vencer é tomar
vxy tal que vy tenha o mesmo
número de a’s, b’s e c’s. Mas isto não
é possível pela restrição (2): |vxy| 
m.
Portanto, L não é livre de contexto.
Mais Exemplo
L={ww|w{a,b}*} não é LC.
• Considere a cadeia ambm ambm;
• uma possível escolha para uvxyz:
• u= am-l, v=al, x=bm-(n+p), y=bn, z=bpambm
• mas com i (do lema) igual a zero:
• ak bjambm, com k,j<m, e não está em L
• outras escolhas são análogas.
Ainda mais Exemplo!
L={anbj|n=j2} não é LC.
2
• Seja m, do lema e am bm.
• De todas as escolhas possíveis aquelas
que requerem mais cuida-do tem a
forma geral:
2
• u=am -(k1+p), v=ak1, x=apbm-(k2+q), y=bk2 e
z=bq.
• bombeando i vezes obteremos m2+(i-1)k1
a’s e m+(i-1)k2 b’s
• para termos |vy|>1:
• se k1=0 então k2>1 e uma cadeia com m2 a’s
e m-k2 b’s (i=0) não está em L;
• se k2=0 então k1>1 e uma cadeia com m2-k1
a’s e m b’s (i=0) também não está em L;
• se k1,k2>0, com i=0:
(m-k2)2 ≤ (m-1)2
= m2 - 2m + 1
< m2 - k1
• e a cadeia obtida não está em L.
Propriedades das LLCs
• É fechada sobre união, concatenação, fecho
de Kleene e homomorfismo;
• mas não é fechada sob interseção nem
complementação!
• L1={anbncm|n,m≥0}
• L2={anbmcm|n,m≥0}
• L1L2={anbncn|n≥0}
• L1L2=(L1  L2)
Propriedades de Decidibilidade
• Existe algoritmo para decidir se:
• L é vazia ou não;
• L é infinita ou não;
• xL;
• Não existe para:
•
•
•
•
•
L(G)=*
L(G1)L(G2)
L(G1)=L(G2)
L(G) é regular
L(G1)L(G2)=
Máquina de Turing e
Computabilidade
•Máquinas de Turing são os autôma-tos
mais potentes que estudaremos.
•Elas podem computar qualquer fun-ção
computável;
•Há até quem acredite que tudo que é
efetivamente computável é computá-vel por
uma MT.
Outras noções de
computabilidade
•  - cálculo (Church 1933);
• Funções  - recusivas (Gödel 1936);
• Combinadores lógicos (Schönfinkel 1924,
Curry 1929);
• Sistema de Post (Post 1943);
• Máquiinas de Turing (Turing 1936-7).
Tese de Church-Turing
Todos os sistemas acima captam a noção
de computável.
SIMULAÇÃO UNIVERSAL OU PROGRAMAS
COMO DADOS.
Máquina de Turing (Descrição Informal)
├
a
b
b
a
b
a
■
■
■
■
ambos sentidos, lê/escreve
Q
...
Máquina de Turing:
•conjunto finito de estados Q;
•uma fita semi-infinita, isto é, ela é
delimitada à esquerda pelo símbolo ├ e
infinita a direita;
•o cabeçote da fita pode se mover para a
direita e para esquerda da fita e pode
escrever símbolos sobre a fita;
•a entrada da fita é de tamanho finito e
inicialmente está logo após o ├ (à direita);
•as infinitas células a direita da cadeia de
entrada todas também contém o símbolo
especial nulo ■;
•funcionamento começa no estado inicial S
e o cabeçote sobre ├;
•a cada passo a MT lê o símbolo sobre o cabeçote, e dependendo deste símbolo e do
estado corrente, escreve um novo símbolo
nesta célula, move o cabeçote para a
direita ou para a esquerda e entra num novo
estado (função de transição d);
•a MT aceita a cadeia de entrada indo para
um estado especial t e rejeita indo para um
estado especial r;
•para algumas cadeias de entrada a MT
pode funcionar infinitamente sem nunca
aceitá-la ou rejeitá-la.
Uma Máquina de Turing é uma 9-tupla
M = (Q,,,■,├,d,s,t,r) onde:
•Q é o conjunto finito de estados;
• é o alfabeto de entrada (finito);
• é o alfabeto da fita contendo  como um
subconjunto (finito)
•u \ , símbolo nulo;
•├  \ , delimitador à esquerda
•d: Qx  Qxx{L,R}, função de transição
•sQ, estado inicial
•tQ, estado de aceitação
•rQ, estado de rejeição
Restrições:
• Nunca escrever sobre├ e nunca se mover
para fora da fita à esquerda.
• Para todo pQ existe um qQ tal que d(p,├) =
(q,├,R)
• Uma vez que a TM entra no estado de
aceitação/rejeição ela nunca sai.
• Para todo b existe c,c’ e d,d’{L,R} tal
que
d (t,b) = (t,c,d)
d (r,b) = (r,c’,d’)
EXEMPLO:
MT que aceita { anbncn / n 0}.
Informalmente:
•A MTcomeça no estado inicial S, varre a
entrada a direita, checando se é da forma
a*b*c*.
•Ela não escreve no seu caminho
(formalmente ela escreve o que leu).
•Até encontrar o primeiro ■, daí troca este
símbolo por um delimitador à direita .
•Agora a MT varre a fita a esquerda
apagando o primeiro c que encontra, então o
primeiro b e também o primeiro a.
•A MT varre a direita apagando um a, um b,
e um c.
•A MT continua indo da direita para
esquerda (e vice-versa) apagando uma
ocorrência de cada letra a cada passo.
• Se em algum passo ela encontra uma
ocorrência de um símbolo e nenhuma
de outra, ela rejeita a cadeia.
• Senão, ela vai apagar todas as letras e
no passo final terá somente nulos
entre├ e , neste ponto a MT aceita a
cadeia.
Formalmente:
Q={s,q1,…,q10,t,r} ={a,b,c} ={,■,}
Função de transição:
S
q1
q2
q3
q4
q5
q6
q7
q8
q9
q10
├
a
(S,├,R) (S,a,R)
_
(r, _ , _ )
_
(r, _ , _ )
(t, _ , _ ) (r, _ , _ )
(r, _ , _ ) (r, _ , _ )
(r, _ , _ ) (q6,■,L)
(q7,├,R) (q6,a,L)
_
(q8,■,R)
_
(q8,a,R)
_
_
_
_
b
(q1,b,R)
(q1,b,R)
(r, _ , _ )
(r, _ , _ )
(q5,■,L)
(q5,b,L)
_
(r, _ , _ )
(q9,■,R)
(q9,b,R)
_
c
(r, _ , _ )
(q2,c,R)
(q2,c,R)
(q4,■, L)
(q4,c,L)
_
_
(r, _ ,_ )
(r, _ , _ )
(q10,■,R)
(q10,c,R)
■

(q3,,L)
_
(r, _ , _ )
_
(q3,,L)
_
(q3,■,L)
_
(q4,■,L )
_
(q5,■,L)
_
(q6,■,L)
_
(q7,■,R) (t, _ _ )
(q8,■,R) (r, _ , _ )
(q9,■,R) (r , _, _ )
(q10,■,R) (q3,,L)
•Configuração inicial (S,├ x■,o)
•■ representa um número infinito de ■’s
•0 significa que a máquina está varrendo o
delimitador ├
•Uma MT aceita uma cadeia de entrada x*
se (S,├ x■,0) * (t,y,n) para algum y e n e
•rejeita se (S,├ x■,0)*(r,y,n) para algum y e
n.
•M pára para uma entrada x se ela aceita x
ou rejeita x. M pode ficar rodando infinitamente com a entrada x.
•O conjunto L(M) representa o conjunto de
todas as cadeias aceitas por M.
• Um conjunto de cadeias é Recursivamente Enumerável (RE) se é L(M) para
alguma máquina de Turing M, e
• Recursivo se é L(M) para alguma má-quina
de Turing M que pára em todas as
entradas.
Máquinas de Turing com múltiplas fitas
•Fitas extras não adicionam poder
computacional
├ a a b b b a ■ ■ ■ ...
├ b b a b b a a ■ ■ ...
├ a b b a b a a ■ ■ ...
Q
•Uma MT com 3 fitas é similar a MT com
uma fita exceto que a de 3 fitas tem as 3
fitas e 3 cabeçotes de leitura.
•Em cada passo a máquina lê os três
símbolos sobre seus cabeçotes, e baseada
nesta informação e no estado corrente, ela
imprime um símbolo em cada fita, move os
cabeçotes (eles não precisam se mover na
mesma direção) e entra num novo estado.
• A função de transição é do tipo
d : Q x 3  Q x 3 x {L,R}3
• Chamemos a MT com 3 fitas de M.
Podemos construir uma máquina de
Turing com uma fita N que simula M
(EXERCÏCIO).
•Máquinas de Turing infinita dos dois
lados.
•Infinitude para ambos os lados não
adiciona poder computacional.
... a b a a b a a b b a a ...
├
a b b a a ...
a b a a b ...
quebre aqui
• Podemos quebrar a fita original em
qualquer lugar e simular a MT em uma
outra MT infinita só a direita com duas
fitas.
• A fita de cima é usada para simu-lar a
MT original quando seu cabeçote está
a direita da quebra, e a trilha de cima
é usada para simular a MT original
quando seu cabeçote está a esquerda
da quebra, movendo-se na direção
oposta.
EXERCÍCIOS
1. Construir uma gramática livre de contexto
para a linguagem formada pelo conjunto de
cadeias sobre {a,b} que não são Palindromes.
Mostre que sua gramática está correta.
2. Construa uma gramática na forma Normal de
Chomsky para o conjunto não vazio de cadeias
com o número balanceado de parênteses ( ) e
colchetes [ ].
3. Descreva a MT N com uma fita que simula M
com três fitas (veja notas de aula).
Gramáticas Tipo 0
( Sem Restrição)
G = (V,T,P ,S) onde as produções de P tem
a forma ab com a e b sendo cadeias
arbitrárias de símbolos da gramática e a 
e.
ad  bd quando ab  P.
L(G) = {W| W  T* e S * W}
EXEMPLO: A gramática geradora de {ai |i é
uma potência positiva de 2}
1)SACaB
2)CaaaC
3)CBDB
4)CBE
5)aDDa
6)ADAC
7)aEEa
8)AE e
• A e B são delimitadores a direita e a
esquerda das formas sentenciais.
•C é um marcador que se move entre A e B
duplicando o número de a’s pela produção
2.
•Quando C alcança o delimitador a direita
B ele se transforma em D ou E pelas
produções 3 ou 4.
•Se D é escolhido ele migra pela produção
S até chegar ao delimita-dor A.
• Neste ponto D se transforma em C pela
produção 6 e o processo co-meça
novamente.
Se E é escolhido, o delimitador a di-reita é
consumido. E migra para a esquerda
pela produção 7 e conso-me o
delimitador a esquerda, resul-tando em
uma cadeia de 2i a’s para i > 0.
Equivalência entre
Gramáticas Tipo 0
e Máquinas de Turing
TEOREMA: Se L é L(G) para uma
gramática tipo 0 G=(V,T,P ,S), então L é
uma linguagem recursivamente
enumerável.
PROVA:
•Construiremos uma máquina de Turing
não-determinística com duas fitas M para
reconhecer L.
•A primeira fita é uma fita de entra-da,
onde a cadeia W será colocada.
•A segunda fita é usada para armaze-nar a
forma sentencial a de G.
M inicializa a com S. Então M repetidamente faz:
1)seleciona, não deterministicamente,
uma posição i em a, 1 i  | a |. Isto é,
começa na esquerda e repetidamente
se move para direita ou seleciona a
posição atual.
2)seleciona aleatoriamente uma produção b de G.
3)se b aparece começando na posição i
de a, troque b por  nesta posição
(shifting over).
4)compare a forma sentencial resultante
com W na fita 1. Se a forma sentencial
for igual a W, aceita w como uma sentença de G. Senão volta para o passo 1.
Obs: Todas e somente as formas
sentenciais de G aparecem na fita 2
quando o passo 2 é executado depois de
algumas escolhas.
• L(M) = L(G) = L então L é
recursivamente enumerável.
q.e.d.
TEOREMA: Se L é uma linguagem
recursivamente enumerável, então L =
L(G) para alguma gramática tipo 0 G.
• a prova é mais elaborada e é omitida
Linguagens Sensíveis ao
Contexto
G = (V,T,P,S) onde as produções em P tem a
forma ab com a e b sendo ca-deias
arbitrárias de símbolos da gra-mática, ae e
b tem que ser pelo menos tão grande (longo)
quanto a.
•O nome sensível ao contexto vem da forma
normal para estas gramáticas onde cada
produção tem a forma
a1Aa2 a1ba2 com be.
Isto é, a variável A pode ser substi-tuída
pela cadeia b somente no contexto a1 _
a2.
Obs: Quase todas as linguagens que
trabalhamos são sensíveis ao con-texto.
As únicas provas que certas linguagens
não são sensíveis ao contexto são
baseadas em diago-nalização.
Autômatos Linearmente
Limitados (ALL)
Um ALL é uma máquina de Turing não
determinística satisfazendo as seguintes
condições:
1)o alfabeto de entrada inclui dois
símbolos especiais ¢ e s, delimita-dores a
esquerda e a direita.
2)o ALL não pode se mover a esquer-da de
¢ e a direita de s, nem pode trocar os
símbolos ¢ e s na fita.
Obs: Um ALL é uma MT que,ao invés
de ter uma fita potencial-mente
infinita para computar, tem somente
uma porção da fita contendo o
símbolo x mais duas células
contendo os delimitado-res.
Existe uma equivalência entre ALL e
gramáticas sensíveis ao contexto.
HIERARQUIA DE CHOMSKY
TEOREMA:
(a) os conjuntos regulares estão conti-dos
propriamente nas linguagens livres de
contexto.
(b) LLC não contendo a palavra vazia estão
contidas propriamente nas LSC.
(c) LSC estão propriamente contidas nos
conjuntos recursivamente enume-ráveis.