http://www.di.ufpe.br/~if114/
WILSON ROSA DE OLIVEIRA
DEPARTAMENTO DE INFORMÁTICA
UFPE
http://www.di.ufpe.br/~wrdo/
Ementa
•
Introdução
Bibliografia
•
Introduction to Automata
• Autômatos Finitos
• Expressões Regulares
Therory, Languages and
•
•
Jeffrey D. Ulman.
•
Gramáticas Regulares
Equivalência entre os
modelos
Propriedades de Linguagens
Regulares
Gramáticas Livre de Contexto
•
Autômatos a Pilha
•
• Máquina de Turing
• Autômatos “Linear - Bounded”
• Linguagens Sensíveis ao
Contexto
• A Hierarquia de Chomsky
Computation John E. Hopcroft,
•
Notas de Teoria da Computação:
Benedito M. Acioly e Benjamin
R.C. Bedregal. Disponível
Eletronicamente em
http:/www.di.ufpe.br/~if114
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  {o,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 }