1
1Automatos - Revisão
1.1Conceitos Auxiliares
1.1.1 Ordenação Lexicográfica
(n1,m1) < (n2,m2) Þ n1 < n2 Ú ( n1 = n2 Ù m1 < m2 )
1.1.2 Ordenação por “Varredura de Matriz”
m\n
0
1
2
3
4
0
1
3
6
10
1
2
5
9
...
2
4
8
...
3
7
12
4
11
1.2Potência de Conjunto
A potência de um conjunto A é o conjunto de todos os subconjuntos de A.
Denota-se por 2S devido ao fato de que quando A é finito |2S | = 2|S|
Obs:
|X| =
# de elementos no conjunto X
# = número
1.3Produto Cartesiano
Sejam A = { 1,2,3 } e B = { 1,2,3 } dois conjuntos.
Produto Cartesiano AxB = { (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) } = { (x,y) | x Î A e y Î B }
1.4Relação
Uma relação a:A®B /* De A em B */ é um subconjunto de AxB. /* a Í AxB */
Podemos ter uma relação de A em A. ( Denota-se A2 )
Uma grafo orientado é um ótimo recurso para representar este tipo de relação:
Ex: SejaA = { a,b,c,d}
a = { (a,b) , (a,d) , (b,c) , (c,c) , (d,b) }
a
b
c
d
b = { (a,b) , (b,a) , ( a,a ) , (d,d) , (c,c) }
a
b
c
d
Obs: Os laços serão representados por uma seta entrando no vértice e sem origem.
1.4.2Inversa
a-1 = { (x,y) | (y,x) Î a }.
1.4.3Composta
Sejam a Í AxB e b Í BxC
b = a°b = { (x,y) Î AxC | $ z Î B , (x,z) Î a Ù (z,y) Î b }
Propriedades:
· (ab)g = a(bg)
· (ab)-1 = b-1a-1
· a-1 = b-1 Û a = b
· (bÈg) = abÈag /* Não vale para Ç */
· (aÈb)-1 = a-1 È b-1
· (aÇb)-1 = a-1 Ç b-1
1.4.4Equivalência
a:S®S é uma Relação de Equivalência se satisfizer as seguintes propriedades:
· Reflexividade: x Î S Þ (x,x) Î a
· Simetria:
(x,y) Î a Þ (y,x) Î a
· Transitividade (x,y) Î a Ù (y,z) Î a Þ (x,z) Î a
2
Ex: S = { a,b,c,d,e } , a Í S2
a
b
c
d
e
1.4.5Blocos
Seja S um conjunto e a uma relação de Equivalência em S.
[x]a = { y Î S | (x,y) Î a } = Bloco x de a em S
Propriedades:
· [x]a Ç [y]a ¹ f Û [x]a = [y]a
· x Î S Þ $ [y]a | x Î [y]a
S=U
[x]
a
·
xÎS
· Para todo x Î S , [x]a ¹ f
1.5Partição
· Uma partição p de S é um conjunto de subconjuntos de S, ( p Í 2S ) , que satisfaz as seguintes
propriedades:
· aÎpÞa¹f
· a,b Î p Ù aÇb ¹ f Þ a = b
·
S=U
aÎ p
[x]a
1.5.1Teorema Partição ⇔ Relação Equivalência (?)
a Í S2 Þ a induz uma Partição pa dada por { [x]a : x Î S }
Uma partição p de S induz Relação de Equivalência ap em S
1.5.2Teorema da Bijeção entre Relações de Equivalência e Partições
Se uma relação de equivalência a Í S2 induz uma partição pa e
esta partição pa induz uma r.e. ap a então :
α = απ α.
Da mesma forma, se uma partição p induz uma r.e ap e esta
relação induz uma partição pap , então:
π = παπ
Em outras palavras:
Seja A o conjunto de todas as Relações de Equivalência em S e
Seja B o conjunto de todas as partições de S. /* A e B são conjunto de Subconjuntos de S */
Seja g Í AxB uma relação que leva cada relação de A as suas partições induzidas e toda partição de B em
suas relações induzidas.
Pelo teorema, g é uma bijeção de A em B.
1.6Potência de Relação
1.6.1Definição
A potência de uma relação a Î S2 é definida assim:
è a0 = { (x,x) | x Î S }
è an+1 = aan , n > 0
ou seja:
ak = aaa....aα0
k vezes
ou ainda:
ak = { (x,y) | $ um passeio de comprimento k ligando x e y }
Seja S = { a,b,c,d,e,f } e a = { (a,a) , (a,b) , (b,e) , (e,a) , (c,c) , (c,d) }
2
3
a
b
e
f
c
d
a
b
e
f
α0
a
b
e
f
c
d
c
d
α1
c
d
a
b
e
f
α2
α3
1.6.2Fecho Reflexivo, Transitivo de α
a* = Ui³0 ai
(x,y) Î a* Û $ Passeio ligando x a y em a
1.6.3Fecho Transitivo de α
a+ = Ui³1 ai
Este fecho exclui a0
a* = a+ È a0
a+ ¹ a* - a0
A diferença acima é devido ao fato de existirem laços no grafo que representa a, e portanto, ao retirarmos a0
de a* estaremos retirando todos os laços. ( Os laços estão em todos os ai , pois com eles podemos criar
passeios de qualquer tamanho ).
1.7Funções
1.8Cardinalidade
1.8.1Finitude
Um conjunto S é finito quando $ k ³ 0 e uma bijeção h:S®{1,2,...,k}
|S| = k
1.8.2Enumerabilidade
S é enumeravel Û S é finito Ú $ bijeção h:S®{1,2,3,...}
Para mostrar que S2 , Racionais, AÈB são enumeráveis, use ídeia baseadas na ordenação por varredura da
matriz.
1.8.3Relação de Desigualdade ( ≤ ) entre conjuntos infinitos
Existe uma definição mais genérica para a relação “menor que” que pode ser usada entre conjuntos infinitos:
Sejam A e B dois conjuntos
A £ B Û $ função injetiva f:A®B
1.8.4ℜ não é enumerável
Prova-se por absurdo que [0,1] não é enumerável da seguinte maneira:
Assumindo que [0,1] é enumerável, temos que:
$ uma bijeção h:[0,1] ® N e
$ uma bijeção h’:N ® [0,1]
Cada número real h’(n) pode ser representado por uma seqüência h’(n) = 0.dn1dn2dn3... de dígitos.
Logo, podemos criar uma matriz, contendo todos os números Reais, da seguinte forma:
h’(1)
h’(2)
h’(3)
h’(4)
h’(5)
h’(6)
...
d11
d21
d31
d41
d51
d61
...
d12
d22
d32
d42
d52
d62
...
d13
d23
d33
d43
d53
d63
...
d14
d24
d34
d44
d54
d64
...
d15
d25
d35
d45
d55
d65
...
d16
d26
d36
d46
d56
d66
...
...
...
...
...
...
...
...
Tomemos um número real x em [0,1], cuja seqüência de dígitos S = 0,s1s2s3... seja definida da seguinte
forma:
Para todo n ³ 1
Se dnn = 0 então
sn = 1
4
Senão
sn = 0
Por construção, verifica-se facilmente que este número não está na matriz descrita acima, e portanto $ x Î
[0,1] | $‘ y Î N | h’(y) = x. O que é um absurdo, visto que h’ é uma bijeção de N em [0,1].
4
5
2Linguagens
2.1Alfabeto
2.1.1Definição
Um alfabeto é um conjunto å ¹ f de símbolos com apenas uma restrição: Dada uma seqüência contínua de
Símbolos de å deve ser possível identificar deterministicamente cada um dos símbolos da seqüência.
2.1.2Cadeias
Uma cadeia sobre å é uma seqüência de símbolos s = s1s2...sn , n ³ 0 e si Î å , 0 £ i £ n.
|s| = n, ou seja, o comprimento de s é n.
Quando n=0 temos uma cadeia vazia, que é denotada por e .
2.1.3Concatenação de Cadeias
sm = s1s2...snm1m2...mm . /* sm é a concatenação de s e m. */
|sm| = |s| + |m|
es = se = s
2.1.4Concatenação de Conjunto de Cadeias
Sejam A e B dois conjuntos finitos contendo cadeias sobre å.
AB = { sm | s Î A Ù m Î B }
|AB| £ |A|.|B|
A concatenação de AB é uma espécie de Produto Cartesiano, com a diferença que alguns elementos de AB
podem estar contidos em A ou B. Por isto a desigualdade acima.
Ex: å = {a,b}
A = { a , ab } , B = { a , ba }
AB = { aa , aba , aba , abba } = { aa, aba, abba }
2.1.5Potência de um Alfabeto
å0 = { e }
ån+1 = åån , n ³ 0
Notar a seguinte diferença em relação a potência de relações:
åk = åå....åå0 = åå...å ( Uma vez que se = s )
∑k = Conjunto de cadeias com tamanho k
2.1.6Fechos
å* = Ui³0 åi = Conjunto de todas as cadeias de comprimento finito sobre å
å+ = Ui³1åi
Notar que:
å* = å+ È {e} e å+ = å* - {e}
2.1.7Cadeia Inversa
Seja s = s1s2...sn , n ³ 1
sT = sn...s1
eT = e
Quando s=sT , s é dita palíndroma. Ex: ARARA
2.2Linguagem
2.2.1Definição
Seja å um alfabeto.
Uma linguagem sobre å é um subconjunto de å*.
Denota-se por L. ( L Í å* )
å = { 0,1 }
L = { s | #0(s) = 2n , n Î N } /* Número de zeros em s é par */
LT = Conjunto formado pela transposição de cada uma das palavras de L
2.2.2Forma Sucinta de Definir uma Linguagem
Descrição Informal
L que aceita os números binários Impar na notação própria
L que aceita palavras com um número par de zeros
L que aceita palavras onde não ocorram 3 zeros consecutivos
Obs: O alfabeto utilizado acima é å = {0,1}
2.3Considerações concernentes a Enumerabilidade (?)
· Todo alfabeto é contável
· å* é contável
Descrição Sucinta
1å*1È1
1*È(1*01*01*)*
å*-å*000å*
6
· Toda linguagem sobre å* é contável
· L = { L Í å* | L é linguagem } não é contável
6
7
3Autômato de Estados Finitos - FSA
3.1Definição
Um Autômato de Estados Finitos (Finite State Automata) é um sistema M sobre um alfabeto å definido da
seguinte forma:
M = (Q , å , d , qo , F )
Q = Conjunto de estados, finito e |Q|>0
å = Alfabeto de Entrada
qo = Estado Inicial pertencente a Q
F = Conjunto de Estados Finais ( Pode ser vazio )
d = Função de Transição de Qxå ® Q. ( Como Q e å são finitos, d pode ser representado por uma
tabela finita . com entrada para cada elemento de Qxå)
3.2Equivalente Mecânico (Interpretação Intuitiva)
Um autômato M é uma Maquina que lê uma cadeia sobre å , da Esquerda para Direita, um símbolo por vez e
para cada símbolo lido, ela usa a função d para alterar seu estado corrente.
A Máquina começa no estado q0 é quando termina de ler todos os símbolos da Cadeia ela pode estar em uma
destas situação:
Estado Corrente Î F Þ Cadeia Aceita
Estado Corrente Ï F Þ Cadeia não Aceita.
s1 s2 s3 s4 s5 s6 s7 s8 s9 ...
2
2
1
1
3
1
s1 s2 s3 s4 s5 s6 s7 s8 s9 ...
1
2
2
1
q0
1
3
1
s1 s2 s3 s4 s5 s6 s7 s8 s9 ...
1
q4
d(q0,s1)®q4
2
2
1
1
3
1
1
q1
d(q4,s 2)®q1
d(q1,s 3)®q4
3.3Linguagem Aceita pelo Autômato
3.3.1Definição “Intuitiva”
Seja a seguinte propriedade P(s) definida para uma cadeia s de å* e um Autômato M :
P(s) é Verdadeiro Û s é aceita pelo Autômato M
P particiona å* em dois subconjuntos. O Conjunto de cadeias não aceitas por M, e o conjunto de cadeias
aceitas por M, o qual é chamado de Linguagem aceita por M ou L(M).
3.3.2Definições Auxiliares
Estado da Computação ® Estado q Î Q do autômato + cadeia s Î å* que ainda não foi lida ( Resto da
Fita )
Configuração ® É uma par ordenado (q,x) Î Qxå* que representa um estado de computação.
Espaço de Configurações ® Qxå*, denota-se por zM
Passo Elementar ® Relação de Movimento no espaço de configuração. Denota-se por |- .
(q,x) |¾ (p,y) Û ( x = ay , a Î å ) Ù d(q,a) = p
Todo FSA induz uma Relação de Movimento |- ⊆ ζ2
Fecho Reflexivo Transitivo de | ® É denotado por |¾* , e indica a existência de uma
seqüência de passos elementares que leva uma Configuração a outra:
(q,x) |¾* (p,y) Û $ n ³ 0 | (q0,x0) |¾ (q1,x1) |¾ ... |¾ (qn ,xn) com
(q0,x0) = (q,x) e
(qn,xn) = (p,y)
n é o numero de passos necessários para “chegarmos em (p,y) partindo de (q,x)”
8
3.3.3 Definição Formal de L(M)
Seja M = (Q,å,d,q0,F) um FSA.
A linguagem aceita por M é definida como:
L(M) = { σ ∈ ∑* | (q0,σ) | (p,ε) , p ∈ F }
Seja M = (Q,å,d,q0,F) tal que
Q = { q0 , q1 , q2 },
å={0,1}
q0 = q0,,
F = { q0 , q2 }
Função d
(q0,0)
q0
(q0,1)
q1
(q1,0)
q1
(q1,1)
q2
(q2,0)
q2
(q2,1)
q1
Prova de que 0110 é aceita :
Prova de que 01 não é aceita :
(q0,0110) |¾ (q0,110) |¾ (q1,10) |¾ (q2,0) |¾ (q2,e)
Logo, (q0,0110) |¾* (q2,e ).
e portanto, como q2 Î F, 0110 Î L(M)
(q0,01) |¾ (q0,1) |¾ (q1,e ), mas q1 Ï F,
Logo,
01 Ï L(M)
3.3.4Criação de FSA a partir da Linguagem
:
Exemplo: Seja å = { 0,1 }, criar um Autômato que reconheça apenas as cadeias com um número de
0’s múltiplo de 3
Sugestão Genérica
Sugestão Aplicada ao Exemplo
Criar um ou mais estados que irão representar o q0 = Número de 0’s lidos é múltiplo de 3
fato da propriedade ser válida para a cadeia já
lida. F deverá conter todos estes estados
Analisar os tipos de cadeias que não satisfazem a q1 = É preciso mais um 0 para que o número de
Propriedade, procurando separar todas as
zeros lidos seja múltiplo de 3
situações possíveis, e criar um estado para cada q2 = É preciso mais dois 0’s para que o número
situação. Q deverá conter todos estes estados,
de 0’s lidos seja múltiplo de 3
mais os estados de F.
Desenhar um grafo para representar cada um dos
estados. ( Um vértice para cada estado ).
Usar um retângulo para representar os estados
q0
q1
q2
Finais.
Para cada estado, verificar para cada um dos
símbolos de å, qual o próximo estado. Criar d
com base nesta análise.
0
q0
1
1
1
q1
0
q2
0
Definir o estado inicial com base na situação da
palavra vazia.
Assinar o estado inicial com uma seta
diferenciada. ( Azul com sombras, no caso )
A palavra vazia possui um número de zeros igual
a três, portanto, q0 deve ser o estado inicial.
0
q0
1
1
1
q1
0
q2
0
Se necessário, descreva o autômato,
especificando detalhadamente Q,å, q0, F, d
3.3.5Alguns Exemplos
L(M) = Palavras com número par de 0’s
Q = { q0 , q1 , q2 }
å={0,1}
q0 = q0
F = { q0 }
d = {((q0,0),q0), ((q0,1),q1), ((q1,0),q2),
((q1,1),q1), ((q2,0),q0), ((q2,1),q2)}
L(M) = Palavras com um número par de 0’s e um
número impar de 1’s
8
9
1
q0
1
0
q1
1
0
q3
0
q2
0 1
1
q0
q0 = Número par de zeros
q1 = Número ímpar de zeros
q0 =
q1 =
q2 =
q3 =
0
1
q1
0
# Par de
# Impar de
# Par de
# Par de
0
1
1
0
# Impar de
# Impar de
# Impar de
# Par de
1
0
0
1
3.3.6Propriedades
· O menor autômato que reconhece um determinada linguagem é único.
· Um autômato com apenas 1 estado q0, ou aceita o fecho å* ( F = { q0 } ), ou aceita apenas e ( F = f }.
3.4Teoremas Importantes
3.4.1Um FSA nunca bloqueia
Teorema: Se x ≠ ε e q ∈ Q então ∃ y ∈ ∑*, p ∈ Q tais que (q,x) | (p,y)
Prova:
Como x ¹ e , $ y Î å* , a Î å tais que x = ay.
Como d é uma função, $ p Î Q | d(q,a) = p
Logo, pela construção de |¾
(q,ay) |¾ (p,y)
E portanto, como x = ay, (q,x) |¾ (p,y)
3.4.2A parte não lida da cadeia não influi no movimento
Teorema: Sejam q,p ∈ Q , x,y ∈ ∑*
(q,x) | * (p,y) ⇔ ∃ z ∈ ∑* | x = zy e (q,z) | * (p,ε)
Prova (Þ): Se (q,x) |¾* (p,y) então $ n ³ 0 | (q,x) |¾n (p,y)
Provemos por indução em n:
Base: ( n = 0 )
(q,x) |¾0 (p,y) Þ (q,x) = (p,y) Þ q = p e x = y
Fazendo z = e , y = x temos :
x = ex = zx = zy e
(q,z) = (q,e) |¾0 (q,e) = (p,e)
E portanto:
(q,z) |¾* (p,e)
Passo: ( n > 0 )
Assumindo que a propriedade é válido para n-1 , n > 1
tomemos (q,x) |¾n (p,y)
Como n > 0 ,
(q,x) |¾ (r,t) |¾n-1 (p,y)
Pela Hipótese de Indução $ s Î å* | t = sy e (r,s) |¾* (p,e)
(q,x) |¾ (r,t) Þ $ a Î å | d(q,a) = r e x = at
Portanto, fazendo z = as temos:
x = at = asy = zy e
(q,z) = (q,as) |¾ (r,s) |¾* (p,e) Þ (q,z) |¾* (p,e).
10
Prova (Ü): Se (q,z) |¾* (p,e) então, $ n ³ 0 | (q,z) |¾ (p,e)
Provemos então por indução em n:
Base: ( n = 0 )
Para (q,z) |¾0 (p,e) temos que
q=p,z=e
e ainda, x = zy = ey = y
Portanto:
(q, x) = (p,y) e,
(q,x) |¾0 (p,y) e ainda,
(q,x) |¾* (p,y)
Passo: ( n > 0 )
Supondo que a propriedade seja válida para n-1,
Tomemos (q,z) |¾n (p,e) , x = zy
Como n > 0 ,
(q,z) |¾ (r,t) |¾n-1 (p,e)
Pela hipótese de indução, temos que
(r,t) |¾n-1 (p,e) e x’ = ty Þ (r,ty) = (r,x’) |¾* (p,y)
Por construção,
(q,z) |¾ (r,t) Þ $ a Î å | z = at e d(q,a) = r
Portanto,
Como, x = zy e z = at
(q,x) = (q,aty ) |¾ (r,ty) |¾* (p,y)
Logo,
(q,x) |¾* (p,y)
3.4.3Possibilidade de “quebra” do movimento em duas partes:
n
Teorema: (q,xy) |¾* (p,e) Û $ r Î Q | (q,x) |¾* (r,e) e (r,y) |¾* (p,e)
Prova (Þ): Se (q,xy) |¾* (p,e) então $ n ³ 0 | (q,xy) |¾n (p,e)
Provemos por indução em n:
Base: ( n = 0 )
(q,xy) |¾0 (p,e) Þ q = p e xy = e
Portanto, x = y = e
Tomando r = q temos,
(q,x) = (r,x) = (r,e) |¾ (r,e), logo (q,x) |¾* (r,e)
E ainda,
(r,y) = (q,y) = (p,y) = (p,e) |¾ (p,e), logo (r,y) |¾* (p,e)
Passo: ( n > 0 )
Supondo válido para n-1,
Tomemos (q,xy) |¾n (p,e)
Devemos tratar separadamente estes 2 casos:
Caso 1) x ¹ e
Como n > 0, temos que
(q,xy) |¾ (s,t) |¾n-1 (p,e) , t = ky ( Como x ¹ e , y não é lido )
Pela H.I, $ r’ Î Q | (s,k) |¾* (r’,e) e (r’,y) |¾* (p,e)
Pelo teorema da seção anterior temos:
Se (s,k) |¾* (r’,e) e t=ky então (s,ky) |¾* (r’,y) , logo
(q,xy) |¾ (s,ky) |¾* (r’,y) , e
(q,xy) |¾* (r’,y) , e novamente pelo teorema da seção anterior:
(q,x) |¾* (r’,e)
Portanto, tomando r = r’, temos:
(q,x) |¾* (r,e) e (r,y) |¾* (p,e)
Caso 2) x = e
Neste caso, tomando r = q temos:
(q,x) |¾ (r,x) = ( r,e) , e portanto, (q,x) |¾* (r,e)
E ainda,
(r,y) = (q,ey) = (q,xy) |¾* (p,e), e portanto, (r,y) |¾* (p,e)
10
11
3.5Provando que uma Linguagem L é aceita por um Autômato M
3.5.1Definição de um caso especial
Seja L = { x Î å* | #0(x) º3 0 } /* Número de zeros é côngruo módulo 3 de 0, i.e. múltiplo de 3 */
Seja M definido pelo seguinte esquema:
0
1
q0 1
q1
1
0
q2
0
Mostrar que L(M) = L, i.é, que a linguagem aceita pelo autômato acima é L.
obs: Nas provas deste tipo deve-se sempre tomar o cuidado de usar Hipóteses de Indução fortes o
suficiente para contemplar todos os estados da Máquina, ou classes das cadeias de L..
3.5.2Provando que L(M) ⊆ L
Chamemos de P a propriedade L(M) Í L.
Devemos mostrar que para todo x Î L(M) , x Î L.
Mas x Î L(M) Þ (q0,x) |¾* (p,e) , p Î F .
No caso, (q0,x) |¾* (q0,,e). E portanto,
$ n ³ 0 | (q0,x) |¾n (q0,e).
Podemos então usar indução em n para provar P.
Antes porem, devemos tomar o cuidado de criar uma conjectura mais abrangente:
Vamos mostrar que:
(c.1) (q0,x) |n (q0,ε) ⇒ #0(x) ≡3 0
(c.2) (q1,x) |n (q0,ε) ⇒ #0(x) ≡3 2
(c.3) (q2,x) |n (q0,ε) ⇒ #0(x) ≡3 1
Base: ( n = 0 )
(c.1)
(q0,x) |¾ (q0,e) Þ x = e.
Portanto #0(x) = #0(e) = 0 , e x Î L.
(c.2)
Vacuamente verdade ( q1 não é estado inicial , portanto, é impossível mostrar um
contra-exemplo)
(c.3)
Vacuamente verdade
Passo: ( n > 0 )
Assumamos que P é válido para 0,1,2 ... n-1
(c.1)
(c.2)
(c.3)
Como n > 0 , (q0,x) |¾n (q0,e) Þ (q0,ay) |¾ (p,y) |¾n-1 (q0,e)
Devemos subdividir este caso em outros 2 :
(c.1.1) Para a = 0 temos :
(q0,0y) |¾ ( q1,y) |¾n-1 (q0,e)
Pela H.I (c.2) , temos que #0(y) º3 2, e portanto
#0(0y) º3 0.
(c.1.2) Para a = 1 temos :
(q0,1y) |¾ (q0,y) |¾n-1(q0,e)
Pela H.I (c.1), temos que #0(y) º3 0 , e portanto
#0(1y) º3 0.
Análogo a (c.1)
Análogo a (c.1)
3.5.3Provando que L ⊆ L(M) (?)
Usaremos os seguintes fatos:
#0(x) º3 0 Þ #0(x) = 3n , n ³ 0
Usaremos ainda os seguintes fatos:
(f.1)
d(p,1) = p , p Î Q ( Pela construção do autômato )
(f.2)
(p,1*x) |¾* (p,x) ( Por f.1 )
Base: ( n = 0 )
12
x = 1* , e portanto, por (f.2) , (q0,1*e) |¾* (q0,e)
Passo: ( n > 0 )
Assumamos que a propriedade seja válida para 0,1,...,n-1
Como n > 0 , podemos fazer x = ab , tal que #0(a) = 3 e #0(b) = 3(n-1).
( Vamos dividir x logo depois do 3o zero ).
Desta forma, x = 1*01*01*01*b.
Por (f.2)
(q0,x) = (q0,1*01*01*01*b) |¾ (q0,01*01*01*b)
Por construção
(q0,1*01*01*01*b) |¾ (q1,1*01*01*b)
Por (f.2)
(q1,1*01*01*b) |¾ (q1,01*01*b)
Por construção
(q1,01*01*b) |¾ (q2,1*01*b)
Por (f.2)
(q2,01*b) |¾ (q2,01*b)
Por construção
(q2,01*b) |¾ (q0,1*b)
Por (f.2)
(q0,1*b) |¾ (q0,b)
Pela hipótese de indução
(q0,b) |¾* (q0,e)
E portanto:
(q0,x) |¾* (q0,e)
12
13
4FSA não Determinístico - NFSA
4.1Definição
A única diferença de um NFSA em relação a um FSA é que d , que no FSA é uma função, no NFSA é uma
relação.
4.2Conseqüências de δ ser uma relação
4.2.1N pode bloquear
Uma vez que d não é mais uma função, pode ser que existam q Î Q e s Î å tais que d(q,s) não é definido.
4.2.2N não é determinístico
Podem existir q1 e q2 Î Q tais que q1 ¹ q2 e d(q,s) = q1 e d(q,s) = q2.
4.3Determinando a aceitação de uma cadeia
Quando N recebe uma cadeia de entrada, embora o Estado da Computação a cada passo possa não ser único,
podemos definir uma estratégia ( Existem várias ) mais elaborada para determinar se a cadeia é válida ou
não.
Nos autômatos que são conhecidos como NFSA a estratégia é a seguinte:
Uma cadeia é aceita sse existir alguma seqüência de Passos Elementares que levem o
Autômato a um estado q Î F após a leitura de toda a cadeia.
Ou seja:
L(N) = { x ∈ ∑* | (q0,x) |* (p,ε), p ∈ F }
4.4Validade dos teoremas 3.4.2 e 3.4.3 (?)
4.5Alguns Exemplos
L(N) = Palavras terminadas 00 = å*00
1
q0
L(N) = å*00å* È å*111å*
0,1
0
0
q1
0
q2
q0
0
0,1
0
q2
p1 1
p2
q1
1
p0 1
0,1
Observar que o construção de um NFSA apartir de uma Linguagem é bem mais simples que a de um FSA,
aliás, este processo pode ser facilmente definido por um algoritmo.
14
5Linguagens Regulares
5.1Definição
O conjunto de Linguagens Regulares é o conjunto de todas a linguagens que podem ser aceitas por um FSA
qualquer.
Seja LFSA = { L Í å* | $ FSA M com L = L(M) }
Seja LNFSA = { L Í å* | $ NFSA N com L = L(N) }
Seja LR o conjunto das Linguagens Regulares
LR = LFSA = LNFSA
5.2Teorema de Robin/Scott
Toda linguagem aceita por um NFSA é Regular
5.2.2Idéia por trás da prova
Autômato Não Determinístico
1
q0
Autômato Determinístico Equivalente
1
0
q1
0
0
q2
q0 0
0
q 0, 0
1 q1
q 0,
q 1,
q2
1
Cada estado no NFSA irá representar todas as possibilidades de estados X do FSA que podem ser atingidos
em um passo elementar, a partir de um conjunto de estados Y do mesmo FSA, e de um símbolo a.
Quando não existir nenhum estado que é atingido pela leitura do símbolo a, deve-se criar um estado nulo
para garantir que d seja uma função.
5.2.3Definição de um FSA N a partir de um NFSA M
Dado um NFSA M = { Q,å,d,qo,F}
Construímos um FSA N = { Q`,å,d`,{q0},F`} do seguinte modo:
Q`= 2Q ( Q` é o conjunto formado por todos os subconjuntos de Q )
F` = { R Í Q : R Ç F ¹ f }
d` = Q`xå ® Q`
d`(S,a) = UsÎS d(s,a) Í Q , S Í Q , a Î å.
Nas próximas seções mostraremos que L(N) = L(M)
5.2.4Teorema Auxiliar
s Î S , S Í Q , (s,x) |M¾
* (r,e) Û $ R Í Q | (S,x) |n¾ * (R,e) , r Î R
Prova (Þ) :
Base: ( n = 0 )
Quando n = 0 temos que s = r e x = e
Tomando R = S, temos:
(S,x) |n¾ 0 (S,x) = (R,e) , r Î R
Passo: ( n > 0 )
Supondo que a propriedade seja válida para 0,1,2 ... n-1,
Tomemos (s,x) |M¾ n (r,e) , s Î S , S Í Q .
Como n > 0 , temos:
x = ay e (s,ay) |M¾ (t,y) |M¾ n-1 (r,e)
Tomemos (S,ay) |n¾ (T,y)
Pela definição de N:
T = UsÎS d(s,a).
Mas, t = d(s,a), e portanto: t Î T.
Logo, pela hipótese de indução.
(T,y) |n¾ * (R,e) , r Î R
E portanto,
(S,ay) = (S,x) |n¾ (T,y) |n¾ * (R,e) , r Î R \
(S,x) |n¾ * (R,e) , r Î R.
14
15
Prova (Ü):
Base: ( n = 0 )
Como n = 0 temos que : S = R e x = e.
Fazendo s = r temos:
(s,x) = (r,e) |M¾ 0 (r,e)
Passo: ( n > 0 )
Supondo válido para 0,1, ... , n-1.
Tomemos (S,x) |n¾ n (R,e) , r Î R
Como n > 0, temos:
x = ay , (S,ay) |n¾ (T,y) |n¾ n-1 (R,e)
Pela Hipótese de Indução, temos que
$ t Î T | (t,y) |M¾ * (r,e)
mas T = UsÎS d(s,a).
E portanto, temos um s Î S tal que d(s,a) = t.
Logo,
(s,x) = (s,ay) |M¾ (t,y) |M¾ * (r,e) \
(s,x) |M¾ * (r,e) , s Î S
5.2.5Prova de que L(M) ⊆ L(N)
x Î L(M) Þ (q0,x) |M¾ * (p,e) , p Î F
Mas q0 Î {q0 } , e {q0} Í Q.
E portanto, pelo teorema da seção anterior:
$ P Í Q | ({q0},x) |n¾ * (P,e) , p Î P
Mas se p Î F e p Î P
P Ç F ¹ f.
E portanto,
P Î F’
Logo:
x Î L(N)
5.2.6Prova de que L(N) ⊆ L(M)
x Î L(N) Þ ({q0},x) |n¾ * (P,e) , P Î F’
Mas se P Î F’, então P Ç F ¹ f.
Tomemos então p tal que p Î P e p Î F. ( Vamos supor a princípio que F ¹ f )
Pelo teorema da seção anterior temos:
(q0,x) |M¾ * (p,e) , uma vez que q0 é o único elemento de {q0}.
Mas p Î F, e portanto
x Î L(M).
Quando F = f temos que F’ = f, visto que XÇf = f, e portanto, L(M) = L(N) = f
16
6Outros autômatos de estados finitos
6.1ε-NFSA
6.1.1Definição do ε-NFSA
A diferença entre um NFSA e um e-NFSA M = (Q,å,d,q0,F) , é que a relação d é definida sobre QxåÈ{e}
® Q, com isto, o e-NFSA pode mudar a configuração sem consumir entrada.
6.1.2Exemplo
0
q0
1
e
q1
2
e
q2
L(M) = 0*1*2*
6.1.3Relação de Movimento
É análoga a do NFSA, com o acréscimo dos passos elementares que não consomem símbolos.
(q,x) |¾ (p,y) Û [ x = y e p Î d(q,e) ] ou [ x = ay , a Î å , p Î d(q,a) ]
6.1.4Linguagem aceita pelo ε-NFSA
L(M) = { x Î å* | (q0,x) |¾* (p,e) , p Î F }
Ex.: O autômato do exemplo admite a seguinte computação:
(q0,002) |¾ (q0,02) |¾ (q0,2) |¾ (q1,2) |¾ (q2,2) |¾ (q2,e)
Portanto, (q0,002) |¾* (q2,e).
Mas q2 Î F , logo, 002 é aceita.
Seja Le-NFSA = { L Í å* | $ e-NFSA, com L(M) = L }
Lε-NFSA = LREG
6.1.5Demonstração de Lε-NFSA ⊆ LREG
Seja N = (Q,å,d,qo,F) um e-NFSA.
Construiremos um autômato M = (Q,å,d‘,q0,F’) , tal que, L(M) = L(N).
Definiremos uma relação passo-e ( æ ) de Q®Q da seguinte forma:
q æ p Û p Î d( q,e) /* É possível passar do estado q para o estado p sem consumir
símbolo */
No autômato NFSA M, teremos:
p ∈ δ‘(q,a) ⇔ ∃ q’, p’ ∈ Q , tais que , qæ*q’ , p’ ∈ δ(q’,a) e p’æ*p
Graficamente:
q
Û
p
a
q
q’
e*
p’
a
p
e*
F’ = [ F se ε ∉ L(N) ] ou [ F ∪ {q0} se ε ∈ L(N) ]
Teorema 1: (q,x) |n¾ * (p,x) Û q æ* p
Teorema 2: (p,ay) |n¾ * (q,y) Û (p,ay) |M¾ * (q,y)
Prova (Þ):
Sabemos que (p,ay) |n¾ * (q,y) Þ (p,ay) |n¾ n (q,y) , n ³ 0.
Caso 1: ( n = 0 )
Vacuamente verdade, uma vez que é impossível consumir o símbolo a, com n = 0.
16
17
Caso 2: ( n ³ 0 )
(p,ay) |n¾ n (q,y) pode ser rescrito como:
(p0,ay) |¾ (p1,ay) |¾ ... |¾ (pk,ay) |¾ (q0,y) |¾ (q1,y) |¾ ... |¾ (qm,y), onde
p0 = p, qm = q, k ³ 0 , m ³ 0 e n = k + m + 1
Mas,
(p0,ay) |¾ (p1,ay) |¾ ... |¾ (pk,ay) Þ p0 æ* pk
e
(q0,y) |¾ (q1,y) |¾ ... |¾ (qm,y) Þ q0 æ* qm
Temos então que:
p0 æ* pk , q0 Î d(pk,a) , q0 æ* qm
Logo,
q Î d‘(p,a) Þ (p,ay) |M¾ (q,y) Þ (p,ay) |M¾ * (q,y)
Prova (Ü):
Pela construção de M, temos que
Se (p,ay) |M¾ * (q,y) então q Î d(p,a).
Portanto,
(p,ay) |n¾ (q,y) , e (p,ay) |n¾ * (q,y)
Prova de que L(N) Í L(M)
Se x Î L(N) então (q0,x) |n¾ n (p,e) , p Î F , n ³ 0
Caso 1: x ¹ e
Com x ¹ e podemos rescrever (q0,x) |n¾ n (p,e) como:
(q0,a1a2...an) |n¾ (q1,a2...an) |n¾ ... |n¾ (qn,an) |n¾ (p,e) , x = a1a2...an
Pelo Teorema 2, temos que:
(q0,a1a2...an) |m¾ * (q1,a2...an) |m¾ * .... |m¾ * (qn,an) |m¾ * (p,e)
E portanto,
(q0,x) |m¾ * (p,e).
Mas, pela construção, p Î F’.
Logo, x Î L(M).
Caso 2: x = e
Quando x = e temos que q0 Î F’ , e portanto
(q0,x) |m¾ (q0,e) Þ (q0,x) |M¾ * (q0,e) , q0 Î F’ Þ x Î L(M).
6.2FSA-Bidimensional : 2-FSA.
6.2.1Definição
É um autômato determinístico M = (Q,å,d,q0,F) onde d é uma função de Qxå ® Qx{D,E},i.é , a função d,
além de fornecer o próximo estado, indica se a “cabeça de leitura” deve avançar (D) ou recuar (E).
6.2.2Exemplo
Q = { qo,q1,q2 } , å = {0,1} , F = { q2 }
0
1
d
q0
(q0,D)
(q1,D)
q1
(q1,D)
(q2,E)
q2
(q0,D)
(q2,E)
6.2.3Relação de Movimento
Uma configuração no 2-FSA passa a ser uma Tripla (x,q,y) onde:
x = Cadeia já lida
q = Estado atual
y = Cadeia não lida
A relação de movimento no 2-FSA é definida assim:
1. (x,q,ay) , a Î å |¾ (xa,p,y) se d(q,a) = (p,D)
2. (xb,q,ay) , a,b Î å |¾ ( x , p ,bay ) se d(q,a) = (p,E)
Condições de bloqueio conseqüentes da definição acima:
1. Configuração (x,p,e).
2. Configuração (e,q,ay) e d(q,a) = (p,E).
6.2.4Linguagem aceita
L(M) = { x Î å* | (e,q0,x) |¾* (x,p,e) , p $ F }
Observações:
· M pode entrar em um situação de loop ao processar uma cadeia x. Neste caso, x é rejeitada, visto que
não existe n ³ 0 tal que (e,q0,x) |¾ n (x,p,e).
· Se houver um bloqueio na configuração (e,q,x), /* Bloqueio a esquerda */ x é rejeitada.
18
Uma situação de Loop pode ser detectada quando uma mesma configuração é atingida 2 vezes.
6.2.5seqüência de Corte
Usando o autômato do exemplo, vamos mostrar a seqüência de corte da cadeia 101001.
1
q0
S1
0
q1
S2
1
q1
q2
q0
S3
0
q1
S4
0
1
q1
S5
q1
q2
q0
S6
q1
S7
O Gráfico acima representa a seguinte seqüência de movimentos:
(e,q0,101001) |¾ (1,q1,01001) |¾ (10,q1,1001) |¾ (1,q2,01001) |¾ (10,q0,1001) |¾
(101,q1,001) |¾ (1010,q1,01) |¾ (10100,q1,1) |¾ (1010,q2,01) |¾ (10100,q0,1) |¾
(101001,q1,e).
6.2.6seqüências de Corte Válidas
Dada uma seqüência de corte S = <q1,q2,q3,...,qn > , dizemos que S é válida quando:
1. n é impar
2. Para quaisquer qi , qj , i ¹ j , i par, j par , temos que qi ¹ qj
3. Para quaisquer qi , qj , i ¹ j , i par, j par , temos que qi ¹ qj
·
·
Em uma computação na forma (e,q,x) |¾* (x,p,e) , todas as seqüências são válidas.
A primeira e a última seqüência de corte de uma cadeia x tem comprimento 1.
·
O número de seqüências de corte válidas é finito ( Regras 2 e 3 ) e pode ser calculado em função
do número total de estados em Q (n) usando-se a seguinte tabela,: ( Lembre-se que não existem
seqüência válidas com tamanho par )
Comprimento da seqüência
1
3
5
k
Número de seqüências válidas possíveis.
n
n.n.(n-1) = n2.(n-1)
n.n.(n-1)/(n-1)(n-3) = n2.(n-1)2.(n-3)
n2.(n-1)2.(n-2)2. ... .(n-(k-4))2.(n-(n-2))
6.2.7L2-NFSA = LREG
Seja S o conjunto de todas as seqüências de corte possíveis para um autômato 2-NFSA M.
Uma seqüência de corte q será representada por <q0,q1,q2,...,qn>
Para cada a Î å definiremos uma relação Ra e outra relação La, ambas de S ® S, da seguinte forma:
1. <> Ra <> , <> La <>
2. q Ra p se d(q0,a) = (p0,D) e <q1,q2,...,qr> La <p1,p2,...,ps>
3. q Ra p se d(q0,a) = (q1,E) e <q2,...,qr> Ra <p1,...,ps>
4. q La p se d(p0,a) = (p0,E) e <q1,...,qr > Ra <>
5. q La p se d(p0,a) = (p1,D) e <q0,...,qr> La <p2,...,ps>
Construímos um NFSA N equivalente a M da seguinte forma:
N = (Q’,å,d‘,q0’,F’)
Q’= { q | q é uma seqüência de cortes válidas } q0’ = <q0>
F’= { <p> : p Î F } d‘= p Î d‘(q,a) sse q Ra p
18
19
7Gramáticas
7.1Gramáticas Lineares a Direita
7.1.1Definição
É um sistema G = (V,T,S,P), onde
T = Alfabeto /* Terminais */
V = Conjunto Finito de Símbolo, tal que VÇT = f /* Não Terminais */
S = Símbolo Inicial pertencente a V.
P = Relação de V ® (T*V È T* ) /* Produções */
Cada par ordenado (a,b) Î P, pode ser representado como a ® b, onde a é o lado esquerdo e b é o lado
direito da produção.
Notar que nas GLD’s, o lado direito da produção, não pode ter mais de um símbolo não terminal , e além
disto, não podem haver símbolos terminais a direita de símbolos não terminais.
7.1.2Relação de Geração e Linguagem Gerada
Toda Gramática G = (V,T,S,P) induz uma relação ⇒ Í (VÈT)*x(VÈT)*, onde
a Þ b sse a = a1Aa2 , b = a1ga2 , A Î V e (A,g) Î P.
A linguagem de G é L(G) = { x Î T* | S Þ* x }
7.1.3Forma Sentencial e Sentença
Se SÞ*a então
Se a contém não terminais a é uma Forma Sentencial de G
Senão a é uma Sentença de G
7.1.4Exemplo
Gramática G que gera 0+1+ :
G = (V,T,S,P) , onde
T = {0,1}
V = { Z, U }
S=Z
P = { (Z,0Z), (Z,0U), (U,1U), (U,1) }
As produções podem ser escritas da seguinte forma:
Z = 0Z | 0U
U = 1U | 1
Gramática H que gera x Î {0,1}* | #0(x) º3 0
S0 = 1S0 | 0S0 | e
S1 = 1S1 | 0S2
S2 = 1S2 | 0S0
7.2Gramáticas Lineares a Esquerda
São análoga as GLD, com a diferença que no Lado Direito da Produção, não podem haver símbolos
terminais a esquerda de símbolos não terminais.
7.3Forma Normal para GLD
Uma GLD na forma normal (GLD-FN) é uma GLD onde o lado direito da produção não pode ter mais do
que 1 símbolo não terminal.
Portanto, toda produção tem a forma:
A ® aB | B , A,B Î V e a Î T
A ® a | e , a Î T.
20
7.4Equivalência entre GLD e GLD na Forma Normal
7.4.1LGLD ⊆ LGLD-FN
Dada uma gramática GLD G = (V,T,S,P) que gera L(G), construiremos uma gramática GLD-FN G’, e
provaremos que L(G’) = L(G).
G’= (V’,T,S,P’) onde
V’= V È { [wA] | B ® zwA Î P }
P’=
A ® [a] , onde A ® a Î P
[ab] ® a[b] , para todo [ab] Î V’ , a Î T.
[A] ® A
[]®e
Gramática Linear a Direita
Z ® 01Z | U
U ® 1U | 1
Demonstração de Z Þ* 010111
Z Þ 01Z Þ 0101Z Þ 0101U Þ
01011U Þ 010111
GLD na Forma Normal
Z ® [01Z] | [U]
[01Z] ® 0[1Z]
[Z] ® Z
U ® [1U] | [1]
[1Z] ® 1[Z]
[U] ® U
[1U] ® 1[U]
[e] ® e
[1] ® 1[e]
Demonstração de Z Þ* 010111
Z Þ [01Z] Þ 0[1Z] Þ 01[Z] Þ 01[01Z] Þ 010[1Z] Þ
0101[Z] Þ 0101[U] Þ 0101[1U] Þ 01011[U] Þ 01011U
Þ 01011[1] Þ 010111[e] Þ 010111
Provando que L(G) ⊆ L(G’)
Teorema 1: Em G’ , [a] Þ* a , a é uma forma sentencial.
Prova : Por indução no tamanho n de a:
Base: ( n = 0 )
Com n = 0 , a = e \ [a] Þ* a , uma vez que ([e], e) Î P’
Hipótese de Indução: Se k < n e a = a1a2...ak então [a] Þ* a
Passo: ( n > 0 )
Como n > 0 , podemos tomar:
a = ab , onde a Î T e |b| < n.
Por construção, ([ab],a[b]) Î P’, e portanto:
[ab] Þ a[b]
Pela Hipótese de Indução
[b] Þ* b
Logo.
[ab] Þ a[b] Þ* ab \ [ab] Þ* ab \ [a] Þ* a
Devemos mostrar que se x Î L(G) , então x Î L(G’) , ou seja,
Se S Þ* x em G então S Þ* x em G’. /* Representarei Þ em G , por GÞ */
Infelizmente, a conjectura acima, não é forte o suficiente para que possamos usar indução
diretamente. Por isto, criaremos uma conjectura mais abrangente ( Este tipo de estratégia é bastante
usado em provas na teoria dos autômatos ):
Se S GÞn a então S G’Þ* a , onde n ³ 0 e a é uma Forma Sentencial em G.
Base: ( n = 0 )
S GÞ0 a \ a = S \ S G’Þ0 a
Passo: ( n > 0 )
Supondo que a propriedade seja verdadeira para n-1, tomemos S GÞn a
Temos então que:
S GÞn-1 yA GÞ yz = a , onde A ® z Î P.
Pela H.I:
S G’Þ * yA.
Pela Construção, A ® z Î P Þ A ® [z] Î P’, e portanto
yA G’Þ y[z]
Pelo Teorema 1,
y[z] G’Þ yz
Portanto,
S G’Þ* a
Notar que a = x é apenas um caso particular do que acabou de ser provado.
20
21
Provando que L(G’) ⊆ L(G)
Teorema 2: Se A G’Þ* w[a] então A GÞ* wa.
Demonstrando que: Se S G’Þn x , n ³ 0 então S GÞ* x , x Î T*
Pela construção de G’, a única produção cujo lado direito não possui um Não
[e] Þ e, portanto, podemos dizer que:
S G’Þ* x[e] Þ xe = x .
Pelo Teorema 2:
S GÞ* xe
Mas xe = x, e portanto
S GÞ* x
terminal é
7.4.2LGLD-FN ⊆ LGLD
É óbvio, visto que a definição de GLD-FN não passa de um caso particular de GDL.
7.5Equivalência entre GLD e GLE
7.5.1Algoritmo para construção de GLE G2 dado uma GLD G1
Dado uma GLD G1 = (V1,T,P1,S1), construiremos uma GLE G2 = (V2,T,P2,S2) da seguinte forma:
V2 = V1 È {S2}
P2 =
B ® Aw quando A ® wB em P1
S2 ® Aw quando A ® w em P1
S1 ® e
Exemplo:
GLD
S ® abA
A ® aB | bC
B ® a | bC
C®b
S Þ abA Þ abaB Þ ababC Þ ababb
S
a
a
bba Ï L(G1)
b
b
GLE
A ® Sab
S2 ® Ba | Cb
B ® Aa
B ® Aa
C ® Ab
A ® Sab
S2 ® Ba
C ® Ab | Bb
C ® Bb
S®e
S2 ® Cb
( “verão clean”)
S®e
S2 Þ Cb Þ Bbb Þ Aabb Þ Sababb Þ ababb
S2
A
a
C
B
B
a
b
a
b
C
a
b
a
b
b
b
b
b
A
a
b
b
a
b
a
b
b
e
a
b
a
b
S2 Þ Ba Þ ??? \ bba Ï L(G2)
b
S
22
7.5.2Teorema Auxiliar
A G1Þ* wB Û B G2Þ* Aw
Prova (Þ): Se A G1Þ* wB então $ n ³ 0 | A G1Þn wB.
Usemos, pois, indução em n.
Base: ( n = 0 )
A G1Þ0 wB É A = B , w = e. , e portanto:
B G2Þ0 B É BG2Þ0 Aw.
Hipótese de Indução: A G1 Þk wB É B G2 Þ* Aw , para k < n.
Passo: ( n > 0 )
Tomemos A G1 Þn wB .
Como n > 0, temos:
A G1 Þn-1 xC Þ xyB , onde xy = w.
Por construção, (B,Cy) Î P2, e portanto
B G2Þ Cy .
Pela Hipótese de Indução
C G2Þ* Ax.
Portanto,
B G2Þ Cy Þ* Axy \ BG2Þ* Axy \ BG2Þ*Aw
Prova (Ü): Análoga a primeira parte.
7.5.3Demonstração de L(G1 ) ⊆ L(G2 )
Tomemos um w Î L(G1) \ $ n ³ 0 | S1 G1 Þn w
Caso 1: Se (S1,w) Î P1 então
Por construção ,
S2 G2Þ S1w Þ ew Þ w \ w Î L(G2)
Caso 2:
Se (S1,w) Ï P1 temos que:
S1 G1Þ* xA Þ xy , xy = w , (A,y) Î P1
Mas (A,y) Î P1 É (S2,Ay) Î P2
Portanto, S2 G2Þ Ay .
Pelo Teorema, S1 G1Þ* xA É A G2Þ* S1x .
Logo, S2 G2Þ Ay Þ* S1xy .
Mas, (S1,e) Î P2 , e portanto:
S1 G2Þ* xy = w \ w Î L(G2).
7.5.4Demonstração de L(G2 ) ⊆ L(G1 )
Análoga a anterior, usando o mesmo teorema ( A volta ).
7.6Gramáticas Lineares e Linguagens Regulares
7.6.1Construção de uma GLD G apartir de um FSA M
Seja um FSA M = ( Q , å , q0 , d , F ) .
Construiremos uma GLD G = ( V , å , P , S ) da seguinte forma:
V=Q
P = { (q,ap) se p = d(a,q) } È { (p,e) se p Î F }
S = q0
Segue da construção que G é GLD.
Exemplo:
Autômato FSA
Gramática G
1
1
1,0
q0
q1
q2
0
0
q0 ® 1q0 | 0q1 | e
q1 ® 1q1 | 0q2
q2 ® 1q2 | 0q2 | e
(q0,110100) |¾ (q0,10100) |¾ (q0,0100) |¾
(q1,100) |¾ (q1,00) |¾ (q2,0) |¾ (q2,e)
q0 Þ 1q0 Þ 11q0 Þ 110q1 Þ 1101q1 Þ 11010q2
Þ 110100q2 Þ 110100e
22
23
7.6.2Demonstração de L(M) ⊆ L(G)
Teorema Auxiliar:
$ n ³ 0 | (q,xy) |¾n (t,y) , x,y Î å*, x ¹ e É q Þ* xt , t Î V.
Base: ( n = 0 )
(q,xy) |¾0 (t,y) É q = t , x = e , Mas
q Þ q , e portanto, q Þ* xt
Hipótese de Indução: (q,xy) |¾k (t,x) É q Þ* xt , quando k < n
Passo: ( n > 0 )
Tomemos (q,xy) |¾n (t,y).
Como n > 0, temos:
(q,awy) |¾ (r,wy) |¾n-1 (t,y) , aw = x , a Î å.
Por construção , (q,ar) Î P, e portanto
q Þ ar
Pela hipótese de indução, r Þ* wt, portanto
q Þ ar Þ* awt \ q Þ* xt.
Demonstração:
Tomemos um x Î L(M) \ (q0,x) |¾* (q,e) , q Î F
Caso 1: x = e
(q0 ,e) |¾* (q,e) É q = q0 , q0 Î F.
Por construção, (q0,e) Î P, logo
q0 Þ e , e portanto, e = x Î L(G).
Caso 2: x ¹ e
Pelo teorema auxiliar, teremos:
(q0,xe) |¾* (q,e) É q0 Þ* xq.
Por construção, (q,e) Î P, e portanto
q0 Þ* xq Þ x \ q0 Þ* x \ x Î L(G).
7.6.3Demonstração de L(G) ⊆ L(M)
7.6.4Construção de um ε-NFSA apartir de uma GLD G
Dado uma GLD G = (V,å,P,S) na forma normal, construiremos um e-NFSA N = ( Q,å,q0,d,F) onde:
Q = V È { q } , onde q Ï V.
q0 = S.
F={q}
((A,a),B) Î d Û (A,aB) Î P
((A,e),B) Î d Û (A,B) Î P
((A,a),q) Î d Û (A,a) Î P
((A,e),q) Î d Û (A,e) Î P
7.6.5Demonstração de L(M) ⊆ L(G)
7.6.6Demonstração de L(G) ⊆ L(M)
7.7Expressões Regulares
7.7.1Definição de Expressões Regulares
Uma Expressão Regular é uma cadeia sobre { å ,f, +, . ,* }, obedecendo as seguintes regras de Geração:
ER ® f | a | ER+ER | ER.ER | ER* , com a Î å e ER.ER podendo ser resumido por ERER
7.7.2Definição Primitiva de Linguagens Regulares (LRs).
Tipo
I
II
III
IV
V
Linguagem Regular L
f
{a} , a Î å
La È Lb, onde La e Lb são Linguagens Regulares
La ° Lb, onde La e Lb são Linguagens Regulares
La* , onde La é uma Linguagem Regular
Expressão Regular que denota L
f
a
a+b
ab
a*
Na definição primitiva, uma Linguagem Regular nada mais era do que as linguagens que podiam ser
denotadas por uma Expressão Regular.
7.7.3Demonstrando que LRs ⊆ Lreg
Caso 1: LRs do Tipo I
Tomando G = ({S},å,f,S) , temos que L(G) = f, portanto f Î Lreg
24
Caso 2: LRs do Tipo II
Tomando G = ({S},å,(S,a),S), temos que L(G) = a, a Î å, e portanto {a} Î Lreg
Caso 3: LRs do Tipo III
Se La Î Lreg então $ Ga = (Va,å,Pa,Sa) | L(Ga) = La
Se Lb Î Lreg então $ Gb = (Vb,å,Pb,Sb) | L(Gb) = Lb
Tomemos então a gramática G = (Va È Vb È {S} , å , Pa È Pb È {(S,Sa),(S,Sb)} ,S).
Temos então, que, L(G) = L(Ga) È L(Gb) = La È Lb
Caso 4: LRs do Tipo IV
Se La Î Lreg então $ Ga = (Va,å,Pa,Sa) | L(Ga) = La
Se Lb Î Lreg então $ Gb = (Vb,å,Pb,Sb) | L(Gb) = Lb
Tomemos então a gramática G = (Va È Vb , å , (Pa È Pb È P) - Q ,Sa), onde,
(A,wSb) Î P sse (A,w) Î Pa
(A,w) Î Q sse (A,w) Î Pa
Temos então, que, L(G) = L(Ga)°L(Gb) = La°Lb
Caso 5: LRs do Tipo V
Se La Î Lreg então $ Ga = (Va,å,Pa,Sa) | L(Ga) = La
Tomemos então a gramática G = (Va È {S} , å , Pa È P ,S), onde,
(A,wSa) Î P sse (A,w) Î Pa
(S,Sa) Î P
(S,e) Î P
7.7.4Demonstrando que Lreg ⊆ LRs
Construiremos expressões regulares para uma gramática qualquer utilizando as seguintes regras:
S ® aA
A ® aB | bC
B ®aB | bC | e
C ® bC | e
Gramática
Expressões Regulares
Ls = aLa
La = aLb + bLc
Lb = aLb + bLc + e
Lc = bLc + e
Resta agora agrupar todas a expressões regulares em uma única:
Lema de Ardin : X = AX + B (I) , e Ï A , então $ uma única solução para X na forma X = A*B
Provando que é solução:
Vamos substituir a solução proposta na equação (I):
A(A*B)+B = A+B + B = (A++e)B = A*B
Provando que é única:
Vamos supor que não seja única.
Seja C tal que : C Ç A*B = f e C ¹ f.
Vamos assumir que T = A*B È C é uma solução para (I)
Substituindo T em (I) temos:
A*B ÈC = A((A*B)ÈC)+B
A*B+C = A((A*B)+C)+B = A+B + AC + B = A+B + B + AC = A*B + AC.
Portanto,
A*B+C = A*B + AC \
(A*B+C)ÇC = (A*B+AC)ÇC \
f + C = f + AC Ç C \
C = AC Ç C \
C Í AC.
Como C ¹ f , podemos tomar um z Î C de comprimento mínimo.
Tomemos também um y Î AC de comprimento mínimo.
Como e Ï A temos que:
|y| > |z| \ Contradição, visto que C Í AC.
Utilizando este resultado para simplificar as Expressões do exemplo:
1. Ls = aLa
2. La = aLb + bLc
3. Lb = aLb + bLc + e
4. Lc = bLc + e
Começamos de "baixo para cima" :
Lc = bLc + e Þ Lc = b*e Þ Lc = b*
Lb = aLb + bLc + e Þ Lb = aLb + bb* + e Þ Lb=aLb + b* Þ Lb=a*b*
La = aLb + bLc Þ La = aa*b* + bb* = a+b*+bb* = (a++b)b*
Ls = a(a++b)b*
24
25
8Propriedades de Linguagens Regulares
8.1Teorema da Iteração
8.1.1Definição
Se L é regular então $ um n ³ 0 tal que para todo x Î L e |x| ³ n temos que:
x = uvw onde:
· |uv| £ n
· |v| ³ 1
· uviw Î L , i ³ 0.
8.1.2Exemplo I
O teorema da iteração é bastante útil para demonstrar que uma determinada linguagem não é regular.
Demonstremos que L = {0n1n | n ³ 0 } não é regular:
Vamos supor por absurdo que L seja regular. Seja k a constante do teorema da iteração.
|uv| £ n É u = 0k , v = 0t , w = 0m1n , onde, k+t+m = n
|v| ³ 1 É k+t+m ³ k+1+m É n ³ k+1+m É n > k+m
Além disto, uviw Î L, i ³ 0 É uw Î L \ 0k0m1n Î L. Contradição, visto que k+m<n
8.1.3Exemplo II
Provemos que L = { 0p : p é primo } não é regular.
Supondo por absurdo que L é regular, tomemos n como a constante do teorema.
Como o número de primos é infinito, tomemos x = 0m , m > n
Temos então que x = uvw \ u = 0k , v=0l , w = 0s , onde k+l+s = m.
Além disto, l ³ 1
Sabemos que 0k0li0s Î L , para todo i ³ 0.
Tomando então i = k+s temos que 0k0l(k+s)0s Î L
Logo, k+l(k+s)+s é primo. Contradição, visto que:
k+1(k+s)+s = (k+s)(l+1) , e como l ³ 1, (k+s)(l+1) = (k+s)x , x ³ 2.
8.1.4Prova
Se L é regular então $ um FSA M = (Q,å,q0,d,F) tal que L(M) = L.
Sabemos que Q ³ 1 e Q é finito.
Tomemos então |Q| como sendo a constante n do teorema.
Seja x = a1...ar Î L(M) , r ³ n. /* Notar que se não existir tal x, a prova já está concluída */
Como x Î L(M) temos que:
(q0,a1...ar) |¾ (q1,a2...ar) |¾ (qr-1,ar) |¾ (qr,e), onde qi Î Q, 0 £ i £ r.
Portanto, como r ³ |Q|, na seqüência de passos que reconhecem x existem pelo menos dois estados
repetidos. Sejam qa , qb, os primeiros estados que se repetem.
Temos então:
(q0,uvw) |¾|u| (qa,vw) |¾|v| (qb,w) |¾* (qr,e) .
8.2Operações em Linguagens Regulares vistas como Conjuntos
8.2.1União
Dado duas linguagens regulares L1 e L2 temos que L1 È L2 é regular.
Prova: Como L1 e L2 são regulares, tomemos r1 e r2 como sendo as expressões regulares que denotam L1 e L2
respectivamente.
Portanto, r1+r2 denota L1ÈL2 \ L1ÈL2 é regular.
8.2.2Concatenação
L1 e L2 regulares Þ L1L2 regular.
Prova: Basta tomar as expressões regulares que denotam L1 e L2 e concatenalas.
26
8.2.3Fecho Transitivo Reflexivo
Se L é regular então L* é regular.
Prova: Trivial.
8.2.4Inverso
Se L é regular então L' = å* - L é regular.
Prova: Dado o FSA M = (Q,å,d,q0,F) que aceita L, temos que o FSA N = (Q,å,d,q0,Q-F) aceita
8.2.5Interseção
å*-L.
Pelo Teorema de DeMorgan sabemos que: L1 Ç L2 = (L1' È L2')', e portanto, pelas propriedades provadas
anteriormente, L1 Ç L2 é regular, quando L1 e L2 também são.
8.2.6Quociente
Sejam L,Z Í å* linguagens.
L/Z = { x Î å* | xy Î L , y Î Z }.
Exemplo:
L
1001
100
11101
11000
11010
Z
001
00
L/Z
1 ( 1001/001 )
110 ( 11000/00)
Se L é regular então L/Z é regular. /* Notar que Z pode ser qualquer linguagem */
Exemplo: L = { 0n | n º5 3 } Z = { 0p | p é primo } Þ L/Z é regular.
Prova: Seja FSA M = (Q,å,q0,d,F) tal que L(M) = L.
Seja M' = (Q,å,q0,d,F') tal que
F' = {p Î Q | (p,y) |¾* (q,e) ,q Î F , y Î Z }
x Î L/Z Þ xy Î L , y Î Z Þ x Î L(M')
x Ï L/Z Þ ...
Dica: Para provar que L é regular podemos tentar primeiro mostrar que L$ é regular, pois, pela
propriedade do quociente, teremos que L/{$} é regular.
8.3Operações utilizando Substituições
8.3.1Substituições
Dado uma linguagem L Í å* e um alfabeto D , que pode ser diferente de å. Uma substituição de L é obtida
da seguinte forma:
Criamos uma função g que associa todo símbolo b Î å a uma Linguagem B Í D*. Ou seja:
g:å®P(D*).
Além disto, determinamos que:
g(e) = {e}
g(f) = f
g(ax) = g(a).g(x)
Temos agora que g:å*®P(D*)
Exemplo: Seja å = {0,1} , D = {a,b} , L = {00,01}.
Tomemos g:å®P(D*) tal que: g(0) = {ab,bb} g(1) = {aa,ba}.
Temos então que:
g(00) = {g(0)g(0) } = { abab , abbb , bbab , bbbb }
g(01) = {g(0)g(1) } = { abaa , abba , bbaa , bbba }
g(L) = { abab , abbb , bbab , bbbb , abaa , abba , bbaa , bbba }
Quando para todo a Î å , g(a) Í D* é regular, dizemos que g é uma Substituição Regular
8.3.2Teorema da Substituição
Sejam å,D alfabetos, L Í å* uma linguagem regular e g:å®P(D*) uma Substituição Regular.
Temos então que g(L) = ÈxÎL {g(x)ÍD*} é regular.
A prova usa o fato de cada g(a) , a Î å , possuir um FSA que reconhece g(a).
26
27
8.3.3Morfismo
Dada uma substituição g:å®P(D*) qualquer.
Se |g(a)| = 1 , a Î å então g é um morfismo. Além disto, como toda Linguagem finita é regular, temos que:
Todo Morfismo é uma substituição regular.
Exemplo da Utilização de Morfismos para provar a irregularidade de uma Linguagem:
Seja L = {anbcn , n ³ 0 }. Vamos supor por absurdo que L é regular.
Tomemos o seguinte morfismo:
f(a) = 0 , f(b) = e , f(c) = 1.
f(L) = { 0n1n | n ³ 0 }.
Portanto, { 0n1n | n ³ 0 } é regular. Absurdo.
Cuidado:
Nem sempre este tipo de construção ajuda a determinar a irregularidade de uma
Linguagem, por exemplo: Dado L = {anban | n ³ 0 } , f(L) = { 02n | n ³ 0 } é
regular.
8.3.4 Morfismo Inverso
Seja f:å®D* um morfismo.
Tomemos f:å*®D* onde f(e) = e . f(ax) = f(a)f(x).
O morfismo inverso de f é uma função f-1:D*®å* tal que dada uma Linguagem L Í D* temos que: f-1(L) =
{ x Î å* | f(x) Î L }.
å = { 0,1 } D = {a,b }
f:å®D* , tal que f(0) = aa f(1) =aba.
L = (ab+ba)*a
Para descobrir f-1 (L) temos que encontrar as cadeias x Î å* , tais que, f(x) Î
(ab+ba)*a.
Estudemos todos os casos possíveis para x Î å*
Caso 1: x = 0y
f(0y) = aaf(y). Notando que as cadeias de L nunca começam com aa,
podemos afirmar que aaf(y) Ï L, e portanto, nenhum x da forma 0y Ï
f-1(L).
Caso 2: x = 1y
f(1y) = abaf(y)
Caso 2.1: y = e
f(1e) = aba \ 1 Î f-1(L)
Caso 2.2: y = 0w
f(10w) = abaaaf(w) \ 10w Ï f-1(L), visto que L não admite 3
"as" consecutivos.
Caso 2.3: y = 1w
f(11w) = abaabaf(w) \ 11w Ï f-1(L).
Portanto, apenas x = 1 Î f-1(L) \ f-1(L) = {1}
Exemplo:
8.3.5Teorema do Morfismo Inverso
Se L é uma Linguagem Regular então f-1(L) também é.
Demonstração: Como L é regular, $ um FSA M = (Q,D,d,q0,F) tal que L(M) = L.
Construiremos um FSA N = (Q,å,d',q0,F) que aceita f-1(L) usando o fato de que x Î f-1(L) sse f(x) Î L.
Dado q,p Î Q , a Î å temos que: d'(q,a) = p sse (q,f(a)) |M¾ * (p,e).
Temos então que:
(q0,x) |n¾ * (p,e) , p Î F Û (q0,f(x)) |M¾ * (p,e), p Î F
28
Utilizando o Teorema para Mostrar que uma Linguagem Não é regular:
Seja L = { anban | n ³ 0} sobre o alfabeto D = {a,b }
Vamos supor que L seja regular.
Tomemos o seguinte morfismo, f:å®D* , å = {0,1,b}
f(0) = a
f(b) = b
f(1) = a
Temos então que f-1(L) = { (0+1)nb(0+1)n }.
Tomemos a linguagem regular L1 = 0*b1* .
Como f-1(L) é regular, temos que: { (0+1)nb(0+1)n } Ç 0*b1* é regular.
Ou seja, 0nb1n , é regular.
Tomemos então o morfismo g, tal que g(0) = 0 , g(b) = e , g(1) = 1.
Temos então que 0n1n é regular. Absurdo.
8.4Problemas de Decidibilidade
8.4.1Algoritmo para Decidir se L = φ
Teorema: Dado um FSA M = (Q,å,d,q0,F) , L(M) = f sse x não aceita nenhum cadeia de
comprimento £ |Q|.
Prova (Þ): L(M) = f então M não aceita qualquer x, inclusive aqueles tais que |x| £ |Q|
Prova (Ü): Vamos supor por absurdo que L ¹ f.
Tomemos então z Î L(M)
Temos que |z| > |Q|, e portanto, existe pelo menos um estado repetido no caminho
percorrido para reconhecer z. Podemos então tomar u como sendo a cadeia
reconhecida ao "tomarmos
o atalho" possibilitado pela ocorrência de estados
repetidos. Desta forma, encontraremos uma cadeia u
onde |u| £ |Q| , contradição.
Algoritmo para Decidir se L = f
Entrada: L regular
Sadia:
[SIM|NAO]
Descrição: Gere um FSA M tal que L(M) = L
Resposta = SIM
Para todo z Î å* onde |z| £ |Q| faca
Se z Î L(M) então
Resposta = NAO
Retorne( Resposta )
8.4.2Algoritmo para Decidir se L é finita
Teorema: L ¹ f é infinita Û $ x em L com |Q| £ |x| £ 2|Q| tal que x é aceita por M = (Q,å,q0,d,F)
Prova (Þ): O maior laço na representação de M tem comprimento |Q|.
Podemos então encurtar z de uma palavra u tal que 1 £ |u| £ |Q|
Seguinte este procedimento, chegaremos a uma palavra x , onde |Q| £ |x| £ 2|Q|.
Prova (Ü): Como |x| > Q , temos um laço em M, e portanto, podemos gerar infinitas cadeias
passando
por este laço.
Algoritmo para Decidir se L é finita
Entrada: L regular
Saída:
[SIM|NAO]
28
29
Descrição: Use o algoritmo anterior para decidir se L = f
Se L = f então
Retorne( SIM )
Para todo z Î å* onde |Q| £ |z| £ 2|Q| faca
Se z Î L(M) então
Retorne(NAO)
Retorne(SIM)
8.4.3Algoritmo para Testar se L1 ⊆ L2
L1 Í L2 Þ L1 Ç L2' = f ( L2' = Inversa de L2 )
Sabemos que X1' é regular, e X1 Ç X2 é regular, quando X1 ,X2 são regulares. Portanto, L1 Ç L2' é regular.
Logo, para decidir se L1 Í L2 basta encontrar L = L1 Ç L2' , e usar o algoritmo 1.4.1 para decidir se L = f .
8.4.4Algoritmo para Testar se L1 = L2
Basta usar o seguinte fato, junto com o algoritmo anterior:
L1 = L2 Û L1 Í L2 e L2 Í L1.
8.5Minimização de Autômatos FSA
8.5.1Eliminação de Estados Inúteis ( Autômato Reduzido )
Dado M = ( Q,å,q0,d,F) , dizemos que um estado p Î Q é útil se e somente se $ x Î å* tal que (q0,x) |¾*
(p,e).
Para encontrar o conjunto Qu de estados úteis de M, basta fazermos uma busca em profundidade no grafo
dirigido que representa M. Um estado q Î Qu se e somente se q aparecer na Árvore de Profundidade de M.
O autômato N reduzido equivalente a M é dado por (Qu,å,du,q0,Fu ), onde Fu = F Ç Qu e du(p,a) = d(p,a).
8.5.2Eliminação dos Estados Indistinguíveis ( Autômato Mínimo )
Dois estados p,q Î Q são indistinguíveis sse p/todo x Î å* temos:
(p,x) |¾* (f,e) , f Î F Û (q,x) |¾* (f',e) , f' Î F.
Teorema: Se p e q são distinguíveis e d(p',a) = p , d(q',a) = q então p'e q' são distinguíveis.
Algoritmo para encontrar estados indistinguiveis:
Seja M = (Q,å,q0,d,F) um FSA.
Seja D um conjunto de pares que conterá todos os pares de estados distinguíveis.
D = (p,q) | p Î F e q Ï F.
Enquanto D estiver aumentando de tamanho de uma iteração para outra faça
Para Todo (p,q) Î QxQ tal que (p,q) Î D faça
Para Todo a Î å faça
p' = d(p,a)
q' = d(q,a)
Se (p',q') Î D então
D = D È (p,q)
I = { (p,q) | (p,q) Ï D } /* Conjunto de estados indistinguíveis */
Para facilitar a execução manual do algoritmo é aconselhável a utilização de uma Matriz Triangular Inferior:
Exemplo:
1
1
q0
q1
0
q1
q2
q3
q4
a
b
b
b
q0
q2
0
a
a
a
q1
I
I
q2
1
1
q3
0
q4
0
a = Entraram em D antes do laço
b = Entraram em D na primeira iteração
c = Entraram em D na segunda iteração
I
q3
I = Indistinguíveis
1
0
30
Para gerar o Autômato Mínimo devemos observar que a Relação de Indistinguibilidade é uma Relação de
Equivalência sobre Q, e portanto, particiona Q em algumas classes [q] , q Î Q.
Construímos o Autômato Mínimo M' = (Q',å,q0',F',d') da seguinte forma:
Q' = { [q] | q Î Q } /* Partição que contém q */
q0' = [q0]
F' = { [f] | f Î F }
d'([q],a) = [d(q,a)]
8.5.3Construção do Autômato Mínimo
Sabendo que a relação de indistinguibilidade "~" é de Equivalência sobre os estados de Q. Denominemos de
[q] a classe do estado q na partição induzida por ~.
Construamos o autômato M'= (Q',å,F',q0',d') onde:
Q' = { [q] : q Î Q }
q0' = [q0]
F' = { [f]: f Î F }
d'([q],a) = [d(q,a)]
8.6Demonstrando que o autômato M' é mínimo e único
8.6.1A relação de Indistinguibilidade ~ é de Equivalência
8.6.2Se q é final ( não final) então todo p ∈ [q] é final (não final)
8.6.3~ é invariável a direita
d(p,a) ~ d(q,a) para todo a Î å
8.6.4L(M) = L(M')
8.6.5[p] ~ [q] se e somente se [p] = [q]
8.6.6Construção de outro autômato mínimo M''
Vamos tomar um autômato mínimo qualquer M''.
Por M'' ser mínimo, temos que |Q''| é mínimo.
Criemos a relação a que associa cada estado q' de M' a um estado s de M''
8.6.7α é um para um
Demonstrar que [p]as , [q]as Þ [p] = [q]
8.6.8α um para um ⊃ |Q''| ≥ |Q'|
8.6.9|Q''| = |Q'|
Como |Q''| ³ |Q'| e |Q''| é mínimo, temos que |Q''| = |Q'|
8.6.10M' e M'' são isomorfos
d'([p],a) a d''(s,a) onde [p] a s
30
31
9Gramáticas Livres de Contexto
9.1Definição
É uma gramática G = (V,å,P,S) onde
VÇå=f
V e å são finitos
SÎV
P Í Vx(VÈå)* , ou seja, as produções podem conter qualquer seqüência de Terminais e Não
Terminais no Lado Direito. /* Aqui está a diferença em relação a GLD */
G induz uma relação de derivação , Þ , onde Þ Í (VÈå)*x(VÈå)* e
a Þ b sse a = a1Aa2 , b = a1ga2 e A®g Î P.
L(G) = { x Î å* : S Þ* x }
Exemplos:
1
2
3
4
Gramática
E ® E + E | E * E | (E) | i
Linguagem Correspondente
Expressões Algébricas contendo
adição,multiplicação e uma variável.
anbnambm com n,m ³ 1
S ® B1B2
B1 ® aB1b | ab
B2 ® aB2b | ab
S ® 0S1S | 1S0S | e
S ® 0S0 | 1S1 | e
Número de 0's é igual ao número de 1's
xxT : x Î (0,1)*
9.2Árvores de Derivação e Ambiguidade
Se uma gramática G admite mais de uma árvore de derivação para uma mesma cadeia x, dizemos que G é
ambígua.
Tomemos o exemplo 1.
A cadeia i+i*i Î L(G) admite duas árvores de derivações:
Árvore de Derivação I
Árvore de Derivação II
E
E
i
E
+
E
E
i
*
E
E
E
i
i
+
*
E
E
i
Portanto G é ambígua.
No entanto, neste caso, é possível construir uma gramática equivalente a G que não é ambígua:
E®E+T|T
T®T*F|F
F ® (E) | i
9.3Propriedade Principal das Gramáticas Livres de Contexto
Seja G = (V,å,P,S) e a Î (VÈå)* : a Þ* b
Temos então que a = a1...an , ai Î (VÈå) , 1£i£n e
b = b1...bn , bi Î (VÈå) , 1£i£n e
ai Þ* bi , 1£i£n.
Pela propriedade acima é que estas gramáticas são chamadas "Livre de Contexto".
32
9.4Ambiguidade: Definição Formal
9.4.1Derivação mais a direita
É uma relação obtida apartir da relação Þ , acrescentado-se a seguinte propriedade:
A cada passo da Derivação, apenas o Não Terminal que estiver mais a direita deve ser consumido:
Exemplo:
E®E+T|T
T ® T*F | F
F ® (E) | a
Produção de (a+a)*a usando a derivação + a direita:
E dÞ T dÞ T * F dÞ T*i dÞ (E)*a dÞ (E+T)*a dÞ (E+F)*a dÞ (E+a)*a dÞ (T+a)*a dÞ (F+a)*a dÞ (a+a)
*a
9.4.2Derivação mais a esquerda
Análoga ao caso anterior
Para produzir (a+a)*a teríamos:
E eÞ T eÞ T * F eÞ (E)*F eÞ (E+T)*F eÞ (T+T)*F eÞ (F+T)*F eÞ (a+T)*F eÞ (a+F)*F eÞ (a+a)*F eÞ
(a+a)*a
9.4.3Caracterização de Gramática Ambíguas
G = (V,å,P,S) é ambigua sse $ x Î L(G) : x admite mais de uma derivação mais a direita.
9.4.4Caracterização de Linguagens Ambíguas
Um linguagem L é ambígua sse toda GLC G : L = L(G), implica G é ambígua.
9.5Operações de Redução sobre uma GLC
9.5.1Eliminação de Improdutivos
Um não terminal A Î V é produtivo sse A Þ* x , para algum x Î å*.
Algorítmo para obter não terminais improdutivos
N0 = å
i=0
Faça
Ni+1 = Ni È { A : A®g em P e g Î Ni* }
i=i+1
Até que Ni = Ni-1 .
Produtivos = Ni
Improdutivos = V - Ni
Gramática sem improdutivos (Gp):
Dado G = (V,å,P,S) Gp = (Vp,å,Pp,S) onde Vp = Produtivos È {S}
Pp = A®g onde A Î Vp e g Î Vp*
Exemplo:
Gramática
S ® Aa | B | D
A ® aA | bA | B
B®b
C ® ab
N0
a,b
N1
a,b,B,C
N2
N3
a,b,B,C,A,S a,b,B,C,A,S
Produtivos: N3
Improdutivos: { D }
Para demonstrar que dado G uma GLC e G' uma GLC sem símbolos improdutivos, L(G) = L(G') basta
demonstrar e usar o seguinte fato:
a GÞ* x , x Î å* sse a G'Þ*x
9.5.2Eliminação de Inalcançáveis
A Î V é alcançável em G sse G Þ* aAb, p/ algum a,b Î (VÈå)*
Algoritmo para obter inalcançáveis.
A0 = { S }
i=0
Faça
Ai+1 = Ai È { B | A ® aBb Î P e A Î Ai }
32
33
i=i+1
Enquanto Ai = Ai-1
Alcançáveis = Ai
Inalcancáveis = V - Ai
Gramática sem Inalcançáveis (Ga):
Ga = (Va,å,Pa,S) onde Va = Alcançáveis
Pa = A ® a onde A ® g Î P e A,g Î {VaÈå)*
Exemplo:
Gramática
S ® Aa | B
A ® aA | bA | B
B®b
C ® ab
N0
S
N1
S,A,B
N2
S,A,B
Alcançáveis = N2
Inalcançáveis = { C }
Gramática Ga
S ® Aa | B
A ® aA | bA | B
B®b
Para demonstrar que L(G) = L(Ga) basta provar e usar o seguinte fato:
Dado a Î (Va Èå*) a GÞ* b sse a GaÞ* b
9.5.3Grámatica Reduzida
Uma GLC G é reduzida sse todo símbolo de G é produtivo e alcançável
Teorema: Dado GLC G = (V,å,P,S) , $ GLC G' = (V',å,P',S') reduzida tal que L(G) = L(G').
Para gerar G' usamos o seguinte método
Passo 1. Eliminar não produtivos
Passo 2. Eliminar não alcançáveis
Para demonstrar que L(G') = L(G) temos que demonstrar ainda que o passo 2 não reintroduz símbolos não
produtivos.
Fato: Se b é não alcançável e A ® aBb Î P então A é não alcançável.
Fato: A aplicação dos passos 1 e 2 na ordem inversa pode não eliminar todos os não alcançáveis.
Exemplo:
S ® AB | a
Þ
A®a
(Passo 2)
S ® AB | a
Þ
A®a
(Passo 1)
S®a
A→a
9.5.4Eliminação de Regras Tipo Cadeia
São regras do tipo A ® B onde A,B Î V.
Algorítmo para Eliminação de RTC.
Para todo A Î V faça
N1(A) = { B : A ® B Î P }
i=1
Faca
Ni+1(A) = Ni(A) È {B:X®B , X Î Ni(A) }
i=i+1
Até que Ni(A) = Ni-1(A)
NA = Ni(A)
Construção da nova gramática sem regras tipo cadeia (Gs)
A ® a Î Ps para todo A ® a Î P e a Ï V
A ® a Î Ps para todo B ® a Î P e a Ï V e B Î NA
Lema: L(G) = L(G')
Exemplo:
Gramática
S ® A|Aa
A®B
B ® C|b
C ® D|ab
D®b
V
S
A
B
C
D
N1
A
B
C
D
φ
N2
A,B
B,C
C,D
D
φ
N3
A,B,C
B,C,D
C,D
-
N4
N5
NX , X ∈ V
A,B,C,D A,B,C,D A,B,C,D
B,C,D
B,C,D
C,D
D
-
9.5.5Eliminação de produções nulas ( A→ε )
Algoritmo para Eliminação de produções nulas
Gramática G'
S ® Aa|b|ab
A ® b|ab
B ® b|ab
C ® ab|b
D®b
34
/* Calcular quais A Î V quais A Þ+ e */
A1 = { X Î V : X ® e Î P }
Ai+1 = Ai È { X Î V : X ® a , a Î Ai* }
Calcular Ai até que Ai = Ai-1
Ne = Ai
Geração da nova gramática (G') :
Se A ® a Î P , a ¹ e , então A ® a Î P'
Se A ® a0X1a2X2...an-1Xnan , onde Xi Î Ne e a1...an ¹ e então
A ® a0a1...an em P'
Exemplo:
Gramática
S ® a | aAbB |B
A ® ab | e
B ® Aa | e
N1
A,B
N2
A,B,S
Nε Gramática G'
A,B,S S ®a | aAbB | B | abB | aAb | ab
A ® ab
B ® Aa | a
9.5.6Ordem das Eliminações
Para Eliminar corretamente todos os casos acima sitados, o algorítmo deve ser aplicado na seguinte ordem:
Passo 1: Eliminar Produções Nulas
Passo 2: Eliminar Regras do Tipo Cadeia
Passo 3: Eliminar Não Produtivos
Passo 4: Eliminar Não Alcançáveis
9.6Forma Normal de Chomsky
9.6.1Definição
Uma GCL G está na Forma Normal de Chomsky sse toda produção de G é da forma A ® BC ou A ® a
( Note que a forma normal de chomsky pura não admite gramáticas onde e Î L )
9.6.2Algoritmo para transformação de um GLC qualquer em uma GLC na FNC
Passo 1:
Passo 2:
Passo 3:
Passo 4:
Passo 5:
Eliminar produções nular
Eliminar regras do tipo cadeia
Reduzir G
P/toda produção A ® w1w2a , a ¹ e, wi Î (VÈå)
Elimine A ® w1w2a e acrescente
A ® w1y e y ® w2a , onde y é um novo não terminal
Repite este procedimento até que para todo A®a Î P , |a| £ 2
Se A ® aB ou A ® Ba ou A ® ab , onde a,b Î å e A,B Î V então
Elimina a produção e acrescente:
A ® XaB ou A ® BXa ou A ® XaXb e
Xa ® a e Xb ® b , onde Xa e Xb são novo não terminais.
9.6.3Exemplo
Gramática após Passo 3
S ® bA | aB
A ® bAA | aS | a
B ® aBAB | bS | ab
Após Passo 4
S ® bA | aB
A ® bY1 | aS | a
B ® aY2 | bS | ab
Y1 → AA
Y2 → BY3
Y3 → AB
Após Passo 5
S ® XbA | XaB
A ® XbY1 | XaS | a
B ® XaY2 | XbS | XaXb
Y1 ® AA
Y2 ® BY3
Y3 ® AB
Xa → a
Xb → b
34
35
9.7Forma Normal de Greiback
9.7.1Definição
Toda produção esta na forma A ® bX1...Xn , n ³ 0, Xi Î V, b Î å.
9.7.2Algoritmo
Para gerar uma Gramática G na Forma Normal de Greiback, vamos assumir que G esteja na Forma Normal
de Chomsky. Além disto, usaremos uma função A que mapeia n números inteiros nos n símbolos não
terminais de G para podermos fazer referência aos não terminais de G de forma ordenada. Teremos, desta
forma, V = { A1 , A2 , ... , An }.
Passo I : Índices Decrescentes
/* Elimina produções onde o lado direito começa com um Não Terminal "maior"
Terminal do lado esquerdo */
Para i = n até 1 faça
Para toda produção Ai ® Aka com k > i faça
Para m = k até (i+1) faça
Para toda produção Am ® b acrescente
Ai ® ba em P
Eliminie Ai ® Aka
Passo II : Eliminar Recursões
/* Elimina produções onde o lado direito começa com um Não Terminal "igual"
do lado esquerdo ( Produção Recursiva ) */
Para cada X Î V que possui alguma produção Recursiva faça
Crie 2 conjuntos cujos elementos são "lados direitos" de produções de X
N = { a1 , .... , ak } /* Lados direitos de produções não recursivas */
R = { Xb1 , .... , Xbt } /* Lados direitos de produções recursivas */
Substitua as produções de X pelas seguintes produções:
X ® a1 | a2 | ... | ak
X ® a1Zx | a2Zx | .... | akZx
Zx ® b1Zx | b2Zx | .... | btZx
Zx ® b1 | b2 | ... | bt
Onde o x de Zx é o índice de X.
/* Note que as substituições acima vêm do fato de que a linguagem gerada por X
+ .... + αk)(β1 + ... + βt )* */
Passo III : Índices Crescencentes
Para j = 2 até n faça
Para toda produção Aj ® Aka , k < j faça
Para toda produção Ak ® b faça
Acrescente A ® ba em P
Elimine Aj ® Aka
Para i = 1 até n faça
Para toda produção Zi ® Aka faça
Para toda produção Ak ® b
Acrescente Zi ® ba em P
Elimine Zi ® Aka
9.7.3Exemplo
G na FNC
A1 ® A2A3
Após Passo I
A1 ® A1A2A1A3
A1 ® aA1A3
A1 ® bA3
A2 ® A3A1
A2 ® A1A2A1
Após Passo II
A1 ® aA1A3
A1 ® bA3
A1 ® aA1A3Z1
A1 ® bA3Z1
A2 ® A1A2A1
A2 ® b
A3 ® A1A2
A2 ® aA1
A2 ® b
A3 ® A1A2
A2 ® aA1
A2 ® b
A3 ® A1A2
Após Passo III
A1 ® aA1A3
A1 ® bA3
A1 ® aA1A3Z1
A1 ® bA3Z1
A2 ® aA1A3A2A1
A2 ® bA3A2A1
A2 ® aA1A3Z1A2A1
A2 ® bA3Z1A2A1
A2 ® aA1
A2 ® b
A3 ® aA1A3A2
A3 ® bA3A2
A3 ® aA1A3Z1A2
que o Não
ao Não Terminal
ser: (α1
36
A3 ® a
A3 ® a
A3 ® a
Z1 → A2A1A3Z1
Z1 → A2A1A3
A3 ® bA3Z1A2
A3 ® a
Z1 ® aA1A3A2A1 A1A3Z1
Z1 ® bA3A2A1 A1A3Z1
Z1 ® aA1A3Z1A2A1 A1A3Z1
Z1 ® bA3Z1A2A1 A1A3Z1
Z1 ® aA1A3A2A1 A1A3
Z1 ® bA3A2A1 A1A3
Z1 ® aA1A3Z1A2A1 A1A3
Z1 ® bA3Z1A2A1 A1A3
36
37
10Automatos com Pilha - PushDown
10.1Definição
10.1.1Componentes
Um Automato com Pilha é um Sistema S = (å,G,Q,q0,F,d,Z0) onde:
å = Alfabeto de Entrada
G = Alfabeto da pilha
Q = Conjunto finito de Estados
q0 Î Q = Estado Inicial
F Í Q = Conjunto de Estados Finais
d = Relação de Qx(åÈ{e})xG em QxG*
Z0 Î G = Simbolo inicial da Pilha.
10.1.2Configuração
Uma configuração de um AP ( Automato com Pilha ) pode ser representada atravéz de uma tripla ( q , x , g )
onde q Î Q é o estado atual, x Î å* é a parte da cadeia de entrada que ainda não foi lida e g Î G* é o
conteudo da pilha ( Lido apartir do topo ).
10.1.3Relação de Movimento
Seja zA = Qxå*xG* o espaço de configurações de um AP A.
Todo AP A induz uma relação de movimento ( |¾ ) sobre zAxzA de forma que:
(q,sx,Za) |¾ (p,x,ba) sse (p,b) Î d(q,s,Z) p,q ÎQ , ZÎG , s Î åÈ{e}, x Î å*, a,b Î G*
10.2Linguagem aceita por um AP A
10.2.1Aceitação por Estado Final
LF(A) = { x Î å* : (q0,x,Z0) |¾* (f,e,a) onde f Î F }
10.2.2Aceitação por Pilha Vazia
LP(A) = { x Î å* : (q0,x,Z0) |¾* (p,e,e) }
10.2.3Para Linguagem Regular L ∃ um AP que aceita L
Basta tomar o FSA N = (å,Q,d,q0,F) que aceita L, e construir, com base nele, o seguinte AP A:
A = (Q,å,{Z0},d',q0,Z0,F)
d'(q,a,Z0) = (p,Z0) sse p=d(q,a)
Teremos então que LF(A) = L
10.3Exemplos
10.3.1Automato a Pilha que aceita L = {0n1n : n ≥ 0 }
Intuição:
Ler todos os zeros e empilhar
Ler todos os 1's desempilhando um 0 para cada 1.
Definir aceitação por Pilha Vazia
Descrição: A = (å,G,Q,d,q0,Z0,F} onde
å={0,1}
G = { 0 , Z0 }
Q = { q0 , q1 , q2 }
F=f
q0 = q0
Z0 = Z0
d é definida da seguinte forma:
(q0,0Z0) Î d(q0,0,Z0)
; Empilha o primeiro zero
(q0,00) Î d(q0,0,0)
; Empilha os outros zeros
(q1,0) Î d(q1,e,0)
; "Advinha" a hora de começa a desempilhar
(q1,e) Î d(q1,1,0)
; Desempilha um 0 para cada 1
(q1,e) Î d(q1,e,Z0)
; Desempilha Z0 para ficar com a pilha vazia
Exemplo de uma seqüência de movimentos para aceitar 0011:
(q0,0011,Z0) |¾ (q0,011,0Z0) |¾ (q0,11,00Z0) |¾ (q1,11,00Z0) |¾ (q1,1,0Z0) |¾ (q1,e,Z0) |¾
(q1,e,e).
38
10.3.2Autômato que aceita L = { x : #a(x) = #b(x) } ⊆ {a,b}*
É claro que L não é regular, uma vez que, L Ç a*b* = { anbn , n³ 0 }
Intuição:
. Empilha a entrada desde que o símbolo de entrada seja igual ao topo da pilha
Desempilha quando topo da pilha ¹ Entrada
A cada momento a pilha por estar em duas situações.
1) a = an , n ³ 0 , neste caso, #a(y) = n + #b(y)
2) a = bn , n ³ 0 , neste caso, #b(y) = n + #a(y)
. Sempre que n = 0 o autômato entra num estado de aceitação
Descrição: A = ( å,G,Q,d,q0,Z0,F} onde
å={a,b}
G = { Z0 , a , b }
Q = { f , q0 }
F={f}
d é definida da seguinte forma:
(q0,sZ0) Î d(q0,s,Z0) , para todo s Î å
(q0,ss) Î d(q0,s,s) , para todo s Î å
(q0,e) Î d(q0,s,a) , onde a Î å - {s} , para todo s Î å.
(f,e) Î d(q0,e,Z0)
Demonstrando que L = Lf(A)
Dado s Î å , definiremos s' como sendo a quando s = b e b quando s = a
Teorema 1: (q0,x,smZ0) |¾k (q0,e,snZ0) , k ³ 0 , s Î å É #s(x) = #s'(x) + (n-m)
Provemos por indução em k
Base: ( k = 0 )
(q0,x,smZ0) |¾0 (q0,e,snZ0) É x = e , sn = sm \ n = m.
Temos então que #s(x) = #s'(x) = 0, visto que x = e
Portanto #s(x) = #s'(x) + n-m.
Hipótese de Indução:
A conjectura é verdadeira para todo i < k
Passo: ( k > 0 )
Como k > 0, temos que:
Caso 1: x = e
Por construção, apenas (f,e) Î (q0,e,Z0) , portanto.
A conjectura é vacuamente verdadeira ( não é possível chegar
q0 sem ler um símbolo de entrada )
Caso 2: x ¹ e
Como k > 0, temos que:
(q0,x,smZ0) |¾ (t,y,a) |¾k-1 (q0,e,snZ0)
Para chegar ao estado f , teriamos que ter Z0 no topo da pilha.
Portanto, t = q0 e x = cy , c Î å, visto que, apenas o passo que
leva ao estado f , não consome qualquer símbolo.
Caso 1: x = sy
Temos então que (q0,sy,smZ0) |¾ (q0,y,a)
Por construção: a = sm+1Z0
Portanto:
(q0,sy,smZ0) |¾ (q0,y,sm+1Z0) |¾k-1 (q0,e,snZ0)
Pela Hipótese de Indução ( t = k-1 ) temos que:
#s(y) = #s'(y) + n-(m+1)
Mas #s(x) = #s(y)+1 e #s'(x) = #s'(y), portanto:
#s(x) = #s'(x) + n-(m+1))+1 = #s'(x) + (n - m)
Caso 2: x = s'y
Temos então que (q0,s'y,smZ0) |¾ (q0,y,a)
Por construção: a = sm-1Z0
(q0,s'y,sm) |¾ (q0,y,sm-1) |¾k-1 (q0,e,snZ0)
Pela Hipótese de Indução:
#s(y) = #s'(y) + (n-(m-1))
Mas #s(x) = #s(y) e #s'(x) = #s'(y)+1, portanto:
#s(x) = #s'(x) - 1 + (n-(m-1)) = #s'(x) + (n-m)
Demonstrando que Lf(A) Í L
Tomemos x Î Lf(A). Temos então que (q0,x,Z0) |¾* (f,e,a).
Por construção, temos que a = e.
Portanto (q0,x,Z0) |¾* (f,e,e) \ (q0,x,Z0) |¾n (f,e,e)
Caso 1: x = e
É claro que x Î L
Caso 2: x ¹ e
Temos que x = sy , s Î å.
Pela construção, temos que:
(q0,sy,Z0) |¾ (q0,y,sZ0) |¾* (q0,e,Z0) |¾ (f,e,e)
.
38
39
Ou seja,
(q0,sy,Z0) |¾ (q0,y,sZ0) |¾n (q0,e,Z0) |¾ (f,e,e)
Pelo Teorema 1, temos que:
#s(y) = #s'(y) -1 = #s'(y) - 1
Como #s(x) = #s(y)+1 e #s'(x) = #s'(y), temos que:
#s(x) = #s'(x) -1 + 1 = #s'(x).
Logo, x Î L.
Demonstrando que L Í LF(A)
Use a volta do teorema 1
10.3.3Autômato que aceita L = { wwT : w ∈ {a,b}* }
(q0,s,Z0) Î d(q0,s,Z0) , todo s Î {a,b}
(q0,sx) Î d(q0,s,x)
(q1,x) Î d(q0,e,x)
(q1,e) Î d(q1,s,s)
(f,e) Î d(q1,e,Z0)
;
; Fase de Empilhamento
; "Advinha" o centro da cadeia
; Fase de Desempilhamento
; Aceitação
F = {f}
Q = {f,q0,q1}
G = {a,b,Z0}
Este autômato funciona com qualquer um dos modos de aceitação.
10.4Algumas propriedades
10.4.1Limite de "visão" do AP em relação a Pilha
(q,x,a) |¾* (p,e,b) É (q,xy,aγ) |¾* (p,y,bγ)
10.5Autômatos com Pilha Determinísticos
10.5.1Propriedade I
|d(q,s,x)| £ 1 , para todo q Î Q , s Î å È {e} , x Î G
Exemplo de Autômato que não satisfaz esta propriedade:
1. (q1,aa) Î (q0,0,a)
2. (q2, aa) Î (q0,0,a)
10.5.2Propriedade II
Se |d(q,a,a)| ³ 1 para algum a Î å , q Î Q então |d(q,e,a)| = 0
Exemplo de Autômato que satisfaz a primeira mas não satisfaz a segunda:
Q = {q0,q1} G = {a,b} å = {0,1}
1. (q1,aa) Î (q0,0,a)
2. (q1,ba) Î (q0,0,b)
3. (q1,ba) Î (q0,e,a)
Quando o autômato estiver apontando para o símbolo "a" ele pode escolher tanto a regra 1 quando a 3 para
prosseguir. ( Indeterminismo ).
A conjunção das Propriedades I e II geram uma condição Suficiênte ( Mas não necessária ) para que um
autômato seja Determinístico, i.é, todo o autômato que satisfaz estas propriedades é Determinístico. No
entanto, podem existir autômatos que não satisfaçam estas propriedades e mesmo assim sejam
Determinísticos.
40
10.6Equivalência entre os modos de Aceitação de um AP
10.6.1Linguagens aceitas por Estado Final ⊆ Aceitas por Pilha Vazia
Dado um AP A = (Q,å,G,q0,Z0,F,d) tal que LF(A) = L , construiremos um AP A' que aceita L por Pilha
Vazia, da seguinte forma:
A' = (Q',å,G ',q0',Z0',F',d') onde:
Q' = Q È { q0' , q'' }
G ' = G È { Z0' }
F' = f
d' contém todas as transições de d'
; Simula d
(q0,Z0Z0') Î d'(q0',e,Z0')
; Coloca um símbolo "atrás" de Z0
(q'',x) Î d'(f,e,x) , para todo f Î F
; "Advinha" quando A está num estado final e
; pula para um estado que esvazia a pilha
(q'',e) Î d'(q'',e,x) , para todo x Î G '
; Esvazia a pilha.
10.6.2Linguagens aceitas por Pilha Vazia ⊆ Aceitas por Estado Final
Dado um AP A = (Q,å,G,q0,Z0,F,d) tal que LP(A) = L , construiremos um AP A' que aceita L por Estado
Final , da seguinte forma:
A' = (Q',å,G ',q0',Z0',F',d') onde:
Q' = Q È { q0' , q'' }
G ' = G È { Z0' }
F' = { f ' }
d' contém todas as transições de d'
; Simula d
(q0,Z0Z0') Î d'(q0',e,Z0')
; Coloca um símbolo "atrás" de Z0
(f ',e) Î d'(q,e,Z0') , para todo q Î Q
; "Advinha" quando a pilha de A está vazia e
; pula para um estado final de A'
10.7Métodos para Geração da Árvore de Derivação
10.7.1Método Bottom-Up
A árvore vai sendo construida das folhas para a raiz.
Por ser determístico, é usado na construção de compiladores.
Idéia do Autômato:
A cada passo o autômato deve executar uma das seguintes ações:
Redução: Se Pilha contém ba ( Sem contar Z ) e $ produção do tipo P ® a então
Desempilhe a
Empilhe P
Shift: Caso não seja possível fazer uma redução então
Leia símbolo que está sob a cabeça de leitura
Empilhe este símbolo
Exemplo: Dada a Gramática : E ® E+E | E*E | (E) | i reconhecer a cadeia i+i*i
Fita:
Pilha:
Oper:
Fita:
Pilha:
Oper:
i+i*i
i+i*i
E*
Shift
i+i*i
i
Shift
i+i*i
E*i
Shift
i+i*i
E
Redução
i+i*i
E+E
Redução
i+i*i
E+
Shift
i+i*i
E
Redução
i+i*i
E+i
Shift
i+i*i i+i*i
E+E
E
Redução Redução
A cadeia é reconhecida quando
a pilha termina apenas com o
Simbolo inicial.
Obs: O topo da pilha está do lado direito.
10.7.2Método Top-Down
A árvore vai sendo construida da raiz para as folhas
É altamente não determinístico: A cada passo o autômato "advinha" qual a produção que deve ser usada.
Fita:
Pilha:
Fita:
Pilha:
i+i*i
E
i+i*i
*E
i+i*i
E+E
i+i*i
E
i+i*i
i+E
i+i*i
i
i+i*i
+E
i+i*i
f
i+i*i
E
i+i*i
E*E
i+i*i
i*E
Obs: O topo da pilha está do lado esquerdo.
40
41
10.8Teorema Fundamental : GLC ≅ AP
10.8.1Linguagens Reconhecidas por AP's ⊆ Linguagen geradas por GLC's
Dado um AP A = (Q,å,G,q0,Z0,F,d) tal que LP(A) = L , construiremos uma Gramática G, tal que L(G) = L
da seguinte forma:
Consideração Importante: Um autômato que aceita por pilha vazia possui um propriedadefundamental, uma
função que descreva o tamanho da pilha a cada passo do autômato, durante a aceitação de uma
cadeia,decresce para 0. Isto significa que existem pontos bem determinados em que a pilha atinge um
tamanho x e depois nunca mais passa de x. Diremos que nestes pontos a pilha "baixa de nível".
A
L
T
U
R
A
P
I
L
H
A
...
7
6
5
4
3
2
1
0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
PASSOS
Último Passo
No exemplo acima, temos um exemplo da funcão citada descrevendo o reconhecimento de uma cadeia, note
que a pilha começa com tamanho 1 e termina em 0. Estão assinalados alguns pontos onde a pilha "baixa de
nível".
Como o AP só pode retirar um elemento da pilha por vez, podemos garantir que saindo do nível máximo,
para chegarmos ao nível mínimo, teremos que passar por todos os níveis
Os símbolos de G terão a seguinte "forma" : [q,A,p] indicando que o Autômato está no Estado q , com A no
topo da pilha e quando a pilha "baixar um nível" o autômato irá para o estado q.
Produções de G: ( Note que elas são altamente não determinísticas )
Tipo 1: S ® [q0,Z0,p] , para todo p Î Q
Tipo 2: [q,x,p] ® s , onde (p,e) Î d(q,s,x) , s Î å È {e} , x Î G
Tipo 3: [q,x,p] ® s[p,x1,q1][q1,x2,q2]...[qm,,xm,r] para todo q1,...,qm Î Q e onde
(p,x1...xm) Î d(q,s,x).
Exemplo:
Dado o autômato a Pilha que aceita L = {0n1n : n ³ 0 }
(q1,0Z) Î d(q,0,Z)
(q1,00) Î d(q1,0,0)
G={0}
(q2,0) Î d(q1,e,0)
Q = {q0,q1,q2}
(q2,Z) Î d(q1,e,Z)
å = {0,1}
(q2,e) Î d(q2,1,0)
(q2,e) Î d(q2,e,Z)
Gramática Equivalente:
S ® [q1,Z,q1] | [q1,Z,q2]
[q2,0,q2] ® 1
; (q2,e) Î d(q2,1,0)
[q2,Z,q2] ® e
; (q2,e) Î d(q2,e,Z)
[q1,0,r] ® e[q2,0,r] , r Î Q ; (q2,0) Î d(q1,e,0)
[q1,Z,r] ® e[q2,0,r] , r Î Q
; (q2,Z) Î d(q1,e,Z)
[q1,Z,q1] ® 0[q1,0,q1][q1,Z,q1]
; (q1,0Z) Î d(q1,0,Z)
[q1,Z,q1] ® 0[q1,0,q2][q2,Z,q1]
[q1,Z,q2] ® 0[q1,0,q1][q1,Z,q2]
[q1,Z,q2] ® 0[q1,0,q2][q2,Z,q2]
[q1,0,q1] ® 0[q1,0,q1][q1,0,q1]
[q1,0,q1] ® 0[q1,0,q2][q2,0,q1]
[q1,0,q2] ® 0[q1,0,q1][q1,0,q2]
[q1,0,q2] ® 0[q1,0,q2][q2,0,q2]
; (q1,00) Î d(q1,0,0)
42
Geração de 0011
S Þ [q1,Z,q2] Þ 0[q1,0,q2][q2,Z,q2] Þ 00[q1,0,q2][q2,0,q2][q2,Z,q2] Þ
[q2,0,q2][q2,0,q2][q2,Z,q2] Þ 001[q2,0,q2][q2,Z,q2] Þ 0011[q2,Z,q2] Þ
0011
00
Demonstração da Equivalência entre Lp(A) e L(G)
Teorema Auxiliar 1: (q,x,A) |¾* (p,e,e) É [q,A,p] Þ* x
Prova: Por indução.
(q,x,A) |¾n (p,e,e) , n ³ 0 É [q,A,p] Þ* x
Base: n = 0
Vacuamente verdadeiro
H.I: A conjectura é verdadeira para n-1
Passo: (q,x,A) |¾ (r,y,a) |¾n-1 (p,e,e) , logo, (r,a) Î (q,s,A) , x = sy
Caso 1: a = e .
Temos então que n=1, p=r, y=e e portanto
(r,e) Î (q,s,A) \ por construção [q,A,r] ® s \
[q,A,p] ® sy \[q,A,p] ® x
Caso 2: a ¹ e.
Temos então que a = x1...xm , m ³ 1 e xi Î G
e (r,x1...xm) Î d(q,s,A). Portanto, por construção:
[q,A,p] ® s[r,x1,r1][r1,x2,r2]...[rm-1,xm,rm] , rm = p.
Como o autômato reconhece por pilha vazia temos:
(r,y,x1...,xm) |¾n-1 (p,e,e) É y = y1...ym e
(r,y1,x1) |¾n1 (r1,e,e)
(r1,y2,x2) |¾n2 (r2,e,e)
...
(rm-1,ym,xm) |¾nm (rm,e,e)
É H.I
É H.I
[r,x1,r1] Þ* y1
[r1,x2,r2] Þ* y2
É H.I
[rm-1,xm,rm] Þ* ym
Temos então que: [q,A,p] Þ* sy1...ym = x
Demonstração de que Lp(A) Í L(G)
x Î Lp(A) É (q0,x,Z0) |¾* (p,e,e) É [q0,Z0,p] Þ* x
Por construção, S Þ [q0,Z0,p] \ S Þ* x \ x Î L(G)
Demonstração de que L(G) Í Lp(A)
Análogo ao caso anterior ( Basta provar a volta do Teorema Auxiliar )
10.8.2Linguagens Geradas por GLC's ⊆ Linguagens Reconhecidas por AP's
Dada uma Gramática G = (V,å,P,S) construiremos um AP equivalente da seguinte maneira: ( Método TopDown )
Q = {q0 } , F = f , Z0 = S , G = V È å
d é definida como:
(q,e) Î d(q,a,a) , a Î å
; Desempilha quando topo pilha = cabeça de leitura
(q,a) Î d(q,e,A) , para todo A Î V : A ® a Î P
Para demonstrar a equivalência usa-se o seguinte fato:
a Þ* x
Û (q,x,a) |¾* (q,e,e)
42
43
11Propriedades de GLC's
11.1Teorema da Iteração Simples
11.1.1Descrição
Seja L uma LLC. Então $ n ³ 1 tal que para todo x Î L com |x| ³ n, existem x1,x2,x3,x4,x5 tais que x =
x1x2x3x4x5 onde:
. |x2x3x4| £ n
.
.
|x2x4| ³ 1
Para todo i ³ 0 , x1x2ix3x4ix5 Î L
11.1.2Demonstração
Se L é LLC então existe GLC G, tal que L = L(G)
Vamos assumir que G está na FNC.
Temos então que a altura da árvore de derivação é diretamente proporcional a largura da cadeia derivada,
uma vez que as produções são do tipo A ® BC ou A ® b e portanto, "cada nó da árvore possui no máximo
dois filhos".
Temos ainda que os nós internos da árvore são símbolos não terminais.
Portanto, para cadeias bastante longas teremos caminhos longos partindo da raiz e chegando as folhas. Estes
caminhos, eventualmente terão que possuir não terminais repetidos, visto que a quantidade de não terminais
é finita.
Se a linguagem é finita, basta tomar como constante do teorema o tamanho da maior cadeia + 1.
Se a linguagem é infinita podemos garantir que existem cadeias que "exigem" que suas árvores de derivação
possuam "caminhos com símbolos repetidos". Neste caso, tomamos este caminho e escolhemos os 2
primeiros símbolos repetidos indo de baixo para cima na árvore de derivação. As cadeia x1,x2,...,x5 do
teorema são escolhidas da seguinte forma:
S
A
A
x1
x2
x3
x4
x5
Como G está na FNC e portanto, não existem produções do tipo A®B com A e B não terminais temos que |
x2x4| ³ 1. Além disto, como A é o último símbolo que se repete |x2x3x4| £ k ( constante do teorema ).
11.1.3Exemplo I
Demonstrar que L = {anbncn , n ³ 0 } não é LLC.
Vamos supor por absurdo que L seja LLC
Seja então k a constante do Teorema da Iteração
Tomemos x = akbkck .
Temos então que x Î L e |x| ³ k. Portanto, pelo T.I existem x1,x2,x3,x4,x5 que satisfazem aquelas três
propriedades do teorema.
Estudemos todas as possibilidades para x2 :
k
k
k
aaa...aaa bbb...bbbb ccc...cccc
1
2
3
4 5
44
Caso 1: x2 = am , m ³ 0
|x2x3x4| £ k É x2 e x4 não contém c's.
Como |x2x4| ³ 1 temos que x1x20x3x40x5 contém mais c's do que a's e/ou b's.
Caso 2: x2 contém a's e b's
x1x20x3x40x5 não está em L pois não Ï a*b*c* e L Í a*b*c*
Caso 3: x2 = bm , m ³ 1
x2 e x4 não contém a's.
Como |x2x4| ³ 1 temos que x1x20x3x40x5 contém mais a's do que b's e/ou c's.
Caso 4: x2 contém b's e c's
Análogo ao caso 2
Caso 5: x2 = cm , m ³ 1
x2 e x4 só contém c's.
Como |x2x4| ³ 1 temos que x1x20x3x40x5 contém mais a's do que c's.
11.1.4Exemplo II
Demonstrar que L = {aibjcidj , i,j ³ 0 } não é LLC.
Vamos supor por absurdo que L seja LLC
Seja então n a constante do Teorema da Iteração
Tomemos x = anbncndn .
Temos então que x Î L e |x| ³ n. Portanto, pelo T.I existem x1,x2,x3,x4,x5 que satisfazem as 3 propriedades do
teorema.
Estudemos todas as possibilidades para x2:
Caso 1: x2 contém a's
Então x2x4 não contém c's ou d's uma vez que |x2x4| £ n.
Pelo Teorema, y = x1x3x5 Î L, mas como |x2x4| ³ 1, y contém mais c's ou d's que a's ou b's.
Caso 2: x2 contém b's
Então x2x4 não contém d's uma vez que |x2x4| £ n.
Pelo Teorema, y = x1x3x5 Î L, mas como |x2x4| ³ 1, y contém mais d's que b's.
Caso 3: x2 não contém a's nem b's.
Então x2x4 não contém a's ou b's.
Pelo Teorema, y = x1x3x5 Î L, mas como |x2x4| ³ 1, y contém mais a's ou b's que c's ou d's.
11.2Teorema da Iteração Extendido (Ogden)
11.2.1Exemplo de linguagem que não é GLC e o TI simples não auxilia na prova
Demonstrar que L = {aibjckdl : (i=0) ou (j=k=l)} não é LC
Vamos supor por absurdo que L seja LC
Seja n a constante do teorema:
Caso 1: x não contém a's.
Temos que x = bjckdl e portanto, não importa como escolhamos x1,x2,x3,x4,x5 que
i
i
x1x2 x3x4 x5 , i ³ 0 pertencerá a L, pois, quando i=0 a igualdade entre j,k e l não precisa ser mantida.
Caso 2: x contém a's.
Temos que x = aibncndn , e portanto, sempre é possível escolher x1x2x3x4x5 de
forma a satisfazer
as propriedades do teorema: basta fazer x2 = am , x4 = e , 1 £ m
£ n.
11.2.2Descrição do Teorema ou Lema de Ogden
Para cada LLC $ uma constante n ³ 1 tal que para todo x Î L onde existem ³ n posições marcadas em x.
Existem cadeias x1,x2,x3,x4,x5 tais que x = x1,x2,x3,x4,x5 e valem as seguintes propriedades:
. x2x3x4 tem £ n posições marcadas
.
.
x2x4 tem ³ 1 posições marcadas
Para todo i ³ 0 , x1x2ix3x4ix5 Î L
11.2.3Demonstração do Teorema
Tomemos a gramática G = (V,å,P,S) na FNC que gera uma LLC L.
Chamemos de Não Terminais Marcados os símbolos não terminais T tais que se T Þ* b , b Î å* então b
possui símbolos marcados.
Seja x Î L tal que x = yz.
Tomemos um não terminal A tal que A ® BC Î P e B Þ* y , C Þ* z e y e z tem marcas.
Seja H a árvore de derivação x.
Se houverem h posições marcadas em x então altura de H ³ log(h).
Portanto, em H, existe um passeio a, de S para um terminal a, tal que em a existem pelo menos log(h) não
terminais marcados.
Escolhendo a constante do teorema, n , como sendo 2k+1, onde k = |V| teremos que para todo x com
posições marcadas ³ n, na árvore de derivação de x existe um passeio a de S para um terminal, tal que pelo
menos alguns deles se repetem.
Portanto, podemos tomar x1,x2,x3,x4,x5 da seguinte forma:
S Þ* x1Ax5
44
45
A Þ* x2Ax4
A Þ* x3
Onde A é o último símbolo que se repete e x2x4 possui pelo menos 1 símbolo marcado. Teremos então que
x2x3x4 possuem £ n marcados e x1x2ix3x4ix5 Î L , i ³ 0.
11.2.4Exemplo
Demonstrar que L = {aibjckdl : (i=0) ou (j=k=l)} não é LC
Vamos supor por absurdo que L seja LC
Seja n a constante do teorema:
Tomemos x = abncndn com bncn marcados.
Caso 1: x2 contem a's.
x2 e/ou x4 contém pelo menos um b e nenhum c ou d. Portanto x1x22x3x42x5 Ï L
Caso 2: x2 não contem a's
Caso 2.1 : x2 contem b's
x2x4 não contem d's e portanto x1x22x3x42x5 Ï L
Caso 2.2: x2 não contem b's
x2x4 não contem b's mas contem c's e portanto x1x203x405 Ï L
11.3Operações do Tipo Conjunto
11.3.1Fecho por União
Dados L1 e L2 Î LLC temos que existem gramáticas G1 = (V1,å,S1,P1) e G2 = (V2,å,S2 ,P2) que geram L1 e
L2 respectivamente
Construindo G3 = ( V1ÈV2ÈS3 , å , S3 , P1 È P2 È S3®S1|S2 ) teremos que L(G3) = L(G1)ÈL(G2), e portanto,
LLC é fechado por União.
11.3.2Fecho por Produto
Dados L1 e L2 Î LLC temos que existem gramáticas G1 = (V1,å,S1,P1) e G2 = (V2,å,S2 ,P2) que geram L1 e
L2 respectivamente
Construindo G3 = ( V1ÈV2ÈS3 , å , S3 , P1 È P2 È S3®S1.S2 ) teremos que L(G3) = L(G1)L(G2), e portanto,
LLC é fechado por Produto.
11.3.3Fecho por Kleene
Dados L1 Î LLC temos que existe gramática G1 = (V1,å,S1,P1) que gera L1
Construindo G3 = ( V1ÈS3 , å , S3 , P1 È S3®S1.S3 | e ) teremos que L(G3) = L(G1)*, e portanto, LLC é
fechado pelo Fecho de Kleene.
11.3.4Não validade do Fecho por Interseção
Dadas L1 = {anbnck , n,k ³ 0 } e L2 = {akbncn , n,k ³ 0 } temos que
L1 Ç L2 = {anbncn , n ³ 0 } Ï LLC. No entanto, L1 e L2 Î LLC.
11.3.5Não validade do Fecho por Complemento
Vamos supor por absurdo que para toda L Î LLC , L' = å* - L Î L.
Tomemos L1 e L2 Î LLC. Temos então que L1' e L2' Î LLC.
Pelo fecho da união temos que L1' È L2' Î LLC.
Pela suposição, temos que (L1' È L2' )' Î LLC.
Pelo teorema de DeMorgan (L1' È L2' )' = L1 Ç L2 e portanto L1 Ç L2 Î LLC. Contradição.
11.3.6Fecho por Interseção com Linguagens Regulares
Dadas L Î LLC e R Î LR temos que LÇR Î LLC.
Seja o AP A tal que LF(A) = L
Seja o FSA M tal que L(M) = R
Construiremos um AP A' para reconhecer LÇR da seguinte forma:
Estados de A' = [p,q] onde p é estado de A e q é estado de M.
Relação de transição de A' :
· ([p1,q1],a) Î d'([p,q],a,x) , a Î å sse (p1,a) Î dA(p,a,x) e q1 = dM(q,a).
· ([p1,q],a) Î d'([p,q],e,x) sse (p,a) Î dA(p,e,x)
F' = { [p,q] : p Î FA e q Î FM }
q0' = [p0,q0] : p0 é inicial de A e q0 é inicial de M.
11.4Substituições
11.4.1Fecho por Substituições Livres de Contexto
Se L é LLC e g é uma substituição Livre de Contexto, então g(L) é LLC.
Demonstração:
Seja G a gramática que gera L na FNC
Sejam Ga , para todo a Î å as gramáticas que geram La.
Para construirmos um gramática que gere g(L) basta tomarmos cada produção de G do tipo T®a , a Î å e
substitui-las por T ® Sa onde Sa é o símbolo inicial de Ga.
46
11.4.2Fecho por Morfismo
Segue-se do Fecho por Substituições Livres de Contexto e do fato de todas as Linguagens Finitas serem
Livres de Contexto.
11.4.3Fecho por Morfismo Inverso
Seja h um morfismo de å ® D*
Seja L Í D* uma Linguagem Qualquer
h-1 (L) = { x Î å* : h(x) Î L } é um Morfismo Inverso de L.
Teorema: A Classe LLC é fechada por morfismos inversos.
Demonstração:
Seja L Í D* uma LLC. Existe então um AP, A para aceitar L.
Construiremos um novo AP, M para aceitar h-1(L) da seguinte forma:
Estados de M:
Pares na forma [p,x] , onde p Î QA , x Î D* , e x = h(a) para alguma a Î å.
Movimento (d):
([p,y],a) Î dM([q,ay],e,Z) quando (p,a) Î dA(q,a,Z) onde a Î åÈ{e}
([p,h(a)],Z) Î dM([q,e],a,Z)
Aceitação:
Se aceitação de A for por pilha vazia, M aceita por pilha vazia e estado [q,e]
Exemplo:
L = { ww : w Î {a,b}* }.
Vamos supor por absurdo que L Î LLLC .
Temos então que L1 = { aibjaibj , i,j ³ 0 } Î LLLC uma vez que
L1 = L Ç a+b+a+b+ e a+b+a+b+ é regular.
Seja o seguinte morfismo:
h(a) = h(c) = a
h(b) = h(d) = b
Como L1 é Livre de Contexto, temos que h-1(L1) também é. Portanto,
L2 = h-1(L1) Ç a*b*c*d* é Livre de Contexto, visto que a*b*c*d* é regular.
No entanto, L2 = { aibjcidj , i,j ³ 0}, o que contradiz o fato de L2 Ï LLLC .
Obs: h-1(L1) = (a+c)i(b+d)j(a+c)i(b+d)j.
46
47
12Máquinas de Turing
12.1Definição "Intuitiva"
12.1.1Características principais
A máquina de Turing possui uma fita de tamanho infinito a direita com duas características diferencias em
relação aos FSA's:
· A fita pode tanto ser escrita como lida.
· A cabeça de leitura pode andar tanto para direita quanto para esquerda.
12.1.2Aceitação
Uma cadeia de entrada é aceita por uma máquina M se e somente se M passar por um estado final f. ( É
importante notar que uma cadeia x pode ser aceita mesmo que a cabeça não passe por todos os símbolos
de x ).
12.1.3Condições de parada (bloqueio)
Quando houver uma tentativa de movimento para uma posição anterior a primeira cela (posição) da fita.
Quando a relação d não determinar o próximo movimento. ( A relação d é restrita normalmente a uma
função parcial )
12.1.4Movimentos além de último símbolo da cadeia de entrada
Inicialmente a fita está completamente preenchida por um símbolo denominado branco. Este símbolo não
pode pertencer ao alfabeto da cadeia de entrada. Representaremos este símbolo por b. Desta forma, quando a
cadeia de entrada é copiada para a fita, teremos branco depois do final da cadeia, possibilitando que a
máquina continue se movimentando mesmo depois do ultimo símbolo da cadeia ( desde que d esteja
definido para b ).
12.2Descrição
Uma máquina de turing é um sistema M = (Q,å,G,q0,F,d) onde:
Q = Conjunto de estados ( ¹ f , finito )
q0 Î Q = Estado inicial
F Í Q = Estados Finais
G = Alfabeto de fita.
å Í G = Alfabeto de entrada.
d:QxG ® QxGxD , onde D = {R,L,I} indica a direção de movimento.
R = Right
L = Left
I = No Moviment
Restrições adicionais:
bÎG-å
d é uma função parcial ( Portanto d é determinística )
Maneira de representar um elemento de d
d(q,a) = (p,x,D) , onde:
q = Próximo Estado
a = Símbolo a ser escrito na posição atual
p = Estado anterior
x = Símbolo na posição atual
D = Direção a ser tomada após a escrita de a.
12.3Movimento da Máquina
12.3.1Configuração
Para obter a situação instantânea da máquina devemos possuir as seguintes informações:
Estado atual
Conteúdo da Fita
Posição da cabeça de leitura.
Representaremos estas informações da seguinte forma:
(a,q,b) onde a,b Î G* , q Î Q , conteúdo da fita = ab e a posição da leitora é na cela |a|+1.
Observações:
Como o símbolo a ser lido é o primeiro símbolo de b temos que b ¹ e
O conteúdo da fita na posição |ab|+1 em diante é b .
48
12.3.2Relação de Movimento
Esta relação sobre o espaço de configurações é definida da seguinte forma:
d(q,a) = (p,x,I) , q,p Î Q e a,x Î G
(a,q,ab) |¾ (a,p,xb)
d(q,a) = (p,x,R) , q,p Î Q e a,x Î G
b = e /* Note que existe um símbolo antes de b */
(a,q,a) |¾ (ax,p,B)
b¹e
(a,q,ab) |¾ (ax,p,b)
d(q,a) = (p,x,L) , q,p Î Q e a,x Î G
a = a'b
(a'b,q,ab) |¾ (a',p,bxb)
a=e
Bloqueio.
12.4Linguagem aceita por M
12.4.1L(M) = { x ∈ ∑* : (ε,q0,x) |* (α,f,β) onde f ∈ F }
12.5Exemplo de uma Máquina de Turing
12.5.1Construiremos uma Máquina de Turing para aceitar L = {anbncn , n ≥ 1 } que como se sabe não é uma
LLC.
12.5.2Idéia da Máquina:
aaaaa
Xaaaa
XXaaa
XXXaa
XXXXa
XXXXX
bbbbb
Ybbbb
YYbbb
YYYbb
YYYYb
YYYYY
ccccc
Zcccc
ZZccc
ZZZcc
ZZZZc
ZZZZZ
bbbbb
bbbbb
bbbbb
bbbbb
bbbbb
bbbbb
Fita Inicial
Fita depois do primeiro "loop"
Fita depois do segundo "loop"
...
...
...
12.5.3Estados:
q0 :
Se lendo "a" troca "a" com "X" e procura b andando para direita.
Senão pula para estado q4
q1 :
Troca "b" por "Y" e procura c andando para direita
q2 :
Troca "c" por "Z"
q3 :
Anda para esquerda até encontrar "X" é pula para q0
q4 :
Anda para direita enquanto não encontrar b's nem c's. Se encontrar bloqueia
( Cadeia tem mais
b's ou c's do que a's ). Senão encontrar irá certamente
encontrar um b , neste caso vai para o estado
final f.
f:
Estado Final. ( Quando chega aqui nada mais interessa )
12.5.4Movimento:
Troca a por X e anda para Direita
d(q0,a) = (q1,X,R)
Passa por a's e Y's até encontrar um b
d(q1,a) = (q1,a,R)
d(q1,Y) = (q1,Y,R)
Troca b por Y e anda para Direita
d(q1,b) = (q2,Y,R)
Passa por b's e Z's até encontrar um c
d(q2,b) = (q2,b,R)
d(q2,Z) = (q2,Z,R)
Troca c por Z e fica no mesmo lugar
d(q2,c) = (q3,Z,I)
Anda para esquerda até encontrar um X
d(q3,c) = (q3,c,L)
d(q3,Z) = (q3,Z,L)
d(q3,b) = (q3,b,L)
d(q3,Y) = (q3,Y,L)
d(q3,a) = (q3,a,L)
Move para direita e retorna ao estado q0
d(q3,X) = (q0,X,R)
Finalização: Ao encontrar um Y estando em q0 entra em estado de finalização
d(q0,Y) = (q4,Y,R)
Anda para direita enquanto estiver passando por Y's ou Z's
d(q4,Y) = (q4,Y,R)
d(q4,Z) = (q4,Z,R)
48
49
Se encontrar um b vai para um estado final
d(q4,b) = (f,B,I) , onde f Î F.
50
13Máquinas de Turing Generalizadas
13.1Fita infinita nas duas direções
Simularemos esta máquina I com uma máquina simples M da seguinte forma: ( Note que o problema inverso
é trivial )
Fita infinita nas duas direções
...
-3
-2
-1
1
2
3
Fita infinita a direita
...
1
-1
2
-2
3
-3
4
-4
5
-5
...
...
Trilha 1
Trilha 2
Posição inicial
A trilha 1 da fita de M simula as posições a direita (inclusive) da posição inicial na fita de I
A trilha 2 da fita de M simula as posições a esquerda da posição inicial na fita de I
Para simular as duas trilhas alteraremos o alfabeto de fita da nova maquina:
G(M) = G(I)xG(I)
; Se I tem k símbolos no alfabeto de fita, M terá k2 .
Além disto, teremos para cada um destes símbolos um outro equivalente para indicar o início da fita.
( Teremos 2k2 símbolos no total )
Estados:
Para cada estado q Î Q(I) teremos um estado q+ ( representando que a máquina está focalizando a trilha 1 )
e um estado q- ( foco na trilha 2 ).
Além disto teremos um novo estado q0.
Os estados finais serão os mesmos de I ( acrescentando-se o + e o - )
Movimentos:
Inicialização
dM(q0,[a,b]) = (q0+, [â,b] , I ) ; O símbolo com ^ indica que estamos na primeira cela.
Movimento para direita na máquina I estando na trilha 1
dM( q+ , [a,b] ) = (p+ , [u,b] , R ou I ) se d(q,a) = (p,u,R ou I )
dM( q+ , [â,b] ) = (p+ , [û,b] , R ou I ) se d(q,a) = (p,x,R ou I )
Movimento para esquerda na máquina I estando na trilha 1
dM( q+ , [a,b] ) = (p+ , [u,b] , L ) se d(q,a) = (p,u,L )
dM( q+ , [â,b] ) = (p- , [û,b] , I ) se d(q,a) = (p,x,L )
Para trilha 2 os movimentos são similares (Invertendo esquerda e direita )
13.2Mais de uma Fita
Neste tipo de máquina teremos que d: QxG3 ® (GxD)3.
Idéia da simulação:
Máquina com 3 fitas
Máquina com 1 fita
1
^
1
2
3
4
...
1
2
3
4
...
1
2
3
4
...
Cabeça
R/W
1
1
X
2
X
2
3
4
3
2
3
4
X
4
...
...
...
...
...
...
Trilha 0
Trilha 1 - Setor 1
Trilha 1 - Setor 2
Trilha 2 - Setor 1
Trilha 2 - Setor 2
Trilha 3 - Setor 1
Trilha 3 - Setor 2
Cabeça
R/W
A trilha 0 será usada apenas para marcar o início da fita.
As trilha 1,2,3 simulam as fitas 1,2,3 sendo que:
Setor 1 guarda o conteúdo da fita e o setor 2 a posição em que a fita está.
50
51
Macro Funcionamento da nova máquina:
· Excursiona para direita (3 vezes) para capturar o que cada fita contém nas respectivas posições atuais
( setor 2)
· Consulta d e descobre os novos símbolos e direções
· Excursiona para direita (3 vezes) até as posições atuais de cada fita , altera os valores (setor 1) e muda a
posição (setor 2).
13.3Máquinas Não Determinísticas
Para simularmos uma máquina não deterministica ( d não é restrita a uma função parcial ) usaremos uma
máquina com 3 fitas da seguinte maneira:
· Fita 1: Contém a entrada.
· Fita 2: Rascunho para a entrada.
· Fita 3: seqüência de movimentos que devem ser aplicados na fita 2 ( copia da fita 1).
A chave para o funcionamento desta máquina está na geração sistemática da seqüência na fita 3 de forma a
simular uma busca em largura na árvore que descreve todos os possíveis movimentos da máquina não
determinística.
Para cada seqüência gerada a máquina copia a fita 1 na fita 2 e começa a simular a máquina 2 ( usando os
dados da fita 3 para limitar as opções de d ).
Note que se fosse usada uma busca em profundidade a máquina poderia entrar num estado de loop infinito
antes de chegar a um estado final que estivesse em outra ramificação.
11
6
12
3
1
2
13
14
7
4
8
15
9
16
5
20
Na busca em largura é garantido que o estado 15 será
atingido. Numa busca em pro
fundidade poderia acontecer
de entrarmos em uma situação de loop (estados 12 - 20 11 )
10
13.4Máquinas de Turing como calculadoras
13.4.1Transformando aceitadora (Normal) em calculadora
Dado uma máquina aceitadora que aceita cadeias do tipo x#f(x) podemos construir uma calculadora que
dado uma cadeia de entrada x na fita, substitui x por f(x) da seguinte forma:
Vamos supor que x e f(x) estejam codificados num sistema unário, por exemplo: Se f(x) é função que eleva
um número ao quadrado teremos que f(3) = 9 seria representado por 000#000000000 , ou , 03#(03)2.
Funcionamento da calculadora:
Recebe como cadeia de entrada x.
Acrescenta # na frente de x.
i¬0
Faça
Substitui o que está na frente de # por i
Usa a máquina aceitadora como subrotina para verificar se x#i Î L
Se x#i Î L sai do laço
i¬i+1
52
Apaga fita e coloca i
13.4.2Transformando calculadora em aceitadora
Dado uma calculadora que calcula f(x) tendo x como entrada construiremos uma máquina que aceita x#f(x)
da seguinte forma:
Aceitadora recebe como entrada cadeias do tipo x#f(x)
Salva x#f(x) num rascunho
Extrai o x de x#f(x) que vem antes de #
Usa calculadora como subrotina para calcular f(x)
Concatena x , # , e f(x) e compara este resultado com aquele do rascunho.
Aceita sse o rascunho está igual ao resultado.
13.4.3Dove Tailing
Ao criar uma calculadora apartir de uma aceitadora deve-se tomar o seguinte cuidado:
Ao não aceitar uma cadeia de entrada, a máquina aceitadora pode entrar num estado de loop infinito. Se a
calculadora entrar neste estado antes de ter calculado o valor correto teremos um grande problema. Para
evitar que isto ocorra utiliza-se uma técnica chamada "dove tailing" , onde os números vão sendo testados
"paralelamente"
52
53
14Gramáticas tipo 0
14.1Definição
Nas gramáticas tipo 0 o lado esquerdo das produções pode conter uma cadeia com terminais e não terminais
( igual ao lado direito das gramáticas livre de contexto ). Ou seja, as produções das gramáticas tipo 0 são do
tipo: a ® b , a e b Î (VÈå)* e a ¹ e.
Observe no exemplo a seguir que este tipo de gramática permite que se simule movimentos sobre a cadeia
gerada até um determinado instante.
14.2Exemplo
Gramática para gerar L = {a2i , i ³ 1 } ; "a" elevado a ( 2 elevado a "i" )
S ® ACaB
Ca ® aaC
CB ® DB
aD ® Da
AD ® AC
CB ® E
aE ® Ea
AE ® e
; A e B são marcadores de início e fim
; dobra número de a's e vai para "anda" para direita
; inicia procedimento de fim de "linha"
; "anda" para esquerda
; Prepara para repetir o ciclo de geração de a's
; Para de gerar a's : Apaga marcador de fim (B)
; "anda" para esquerda
; apaga o marcador de inicio
Idéia do funcionamento: Começa sempre gerando 2 a's e vai dobrando a cada passo.
Geração de a23 , ou seja, aaaaaaaa
S Þ ACaB Þ AaaCB Þ
AaaDB Þ AaDaB Þ ADaaB Þ ACaaB
AaaCaB Þ AaaaaCB Þ
AaaaaDB Þ AaaaDaB Þ AaaDaaB Þ AaDaaaB Þ ADaaaaB Þ ACaaaaB
AaaCaaaB Þ AaaaaCaaB Þ AaaaaaaCaB Þ AaaaaaaaaCB
AaaaaaaaaE Þ
AaaaaaaaEa Þ AaaaaaaEaa Þ ... Þ AEaaaaaaaa Þ
eaaaaaaaa = aaaaaaaa
54
15Máquinas de Turing ≅ Gramáticas tipo 0
15.1Simulação de Gramáticas tipo 0 utilizando Máquinas de Turing
Simularemos uma gramática tipo 0, G, utilizando uma Máquina de Turing Não Determinística com 2 fitas:
Fita 1: Entrada
Fita 2: Rascunho
Funcionamento:
Inicializa fita 2 com "S"
Escolhe-se não deterministicamente uma das produções de G e aplica-se a um ponto do conteúdo da fita 2
( Este ponto também é escolhido não determinísticamente ).
Para cada escolha compara conteúdo da fita 2 com fita 1 e aceita se forem iguais.
15.2Simulação de Máquinas de Turing utilizando Gramáticas tipo 0
Vamos assumir que a Máquina de Turing M seja a mais específica possível ( Uma única fita infinita a direita
).
Principal dificuldade: A máquina de turing pode destruir a cadeia de entrada durante o seu funcionamento.
Idéia da gramática G que simula M:
Cada símbolo não terminal será representado por um par [a,x] , onde a é o símbolo inicial da fita e x é o
conteúdo da fita ( Cela da fita ) durante a computação.
Fase 1:
Gera cadeia inicial mais cópia
Gera espaço de rascunho à direita da "fita" ( A máquina pode usar o espaço que vem depois da cadeia de
entrada como rascunho )
S ® q0A0
; gera estado inicial
A0 ® [a,a]A0
; Para todo a Î å ( Permite a geração de qualquer cadeia inicial )
A0 ® A1
A1 ® [e,B]A1
; Permite a geração de uma quantidade qualquer de brancos.
A1 ® e
Fase 2:
Simula operação de M nos segundos elementos de cada par ( Não Terminal )
d(q,x) = (p,y,R) Þ q[a,x] ® [a,y]p , para todo a Î å
d(q,x) = (p,y,I) Þ q[a,x] ® p[a,y] , para todo a Î å
d(q,x) = (p,y,L) Þ [m,z]q[a,x] ® p[m,z][a,y] , para todo a,m Î å
Fase 3:
Se M entra num estado final, G regenera a fita inicial
q[a,x] ® qaq , para todo q Î F
[a,x]q ® qaq
q®e
54
55
16Linguagens Recursivamente Enumeráveis
16.1Definição
LRE = { L Í å* : Existe M.T , M tal que L = L(M) }
16.2Demonstrando que LLLC ⊆ LRE (Propriamente)
16.2.1Mostrando que LLLC ⊆ LRE
Para construir uma Máquina de Turing que simule um Autômato a Pilha P basta usar a generalização que
admite duas fitas:
Fita 1: Cadeia de entrada.
Fita 2: Simulação da Pilha.
16.2.2Mostrando que LLLC ⊆ LRE propriamente
As linguagens L1 = { ww : w Î å* } e L2 = { anbncn , n ³ 1 } não são LLC, no entanto, é possível construir
uma M.T para reconhecelas, portanto LLC ¹ RE.
16.3Propriedades
16.3.1União
Demonstração similar a LLC's
16.3.2Interseção
Sejam duas linguagens recursivamente enumeráveis L1 e L2 e duas máquinas M1 e M2 que as reconheçam.
O funcionamento da Máquina M ( 2 fitas ) que aceita L1 Ç L2 é o seguinte:
Copia fita com cadeia de entrada para fita rascunho
Simula M1 no rascunho.
Se M1 aceita : Copia fita de entrada para rascunho
Se M1 não aceita: rejeita ( Note que se M1 não parar M também não para )
Simula M2 no rascunho.
Aceita sse M2 aceita.
16.4Propriedades Não Válidas (Não Fechadas )
16.4.1 Complemento
16.4.2Produto ?
16.4.3Kleene ?
16.5Exemplo de Linguagem que não pertence a LRE
Toda RE pode ser aceita por uma máquina com 3 símbolos de fita.
Se M possuir k símbolos de fita ( k ³ 3 ) podemos codificar cada símbolo de M em um bloco de 0's , 1's e b's
( Cada bloco com cerca de log(k) símbolos ).
Para simular a máquina original a nova máquina deve seguir os seguintes procedimentos:
Transformar a entrada no código correspondente
Simular: lendo um bloco, obtendo novo estado e o código do novo símbolo , escreve novo bloco e move a
cabeça (de bloco em bloco ).
Máquinas de Turing podem ser descritas por um cadeia de 0's e 1's
Um exemplo de descrição de máquinas de turing usando 0's e 1's é o seguinte:
1 1 1
d
1 1
d
1 1
d
1 1
...
1
1
1
111
Sinaliza inicio/fim da descrição
11
Sinaliza inicio/fim de cada entrada de d
d 0a10b1Oc10d10e
a : Estado atual
b : Símbolo na fita
c : Novo Estado
d : Novo símbolo
e : Direção do Movimento
Desta forma conseguimos uma correspondência entre as máquinas de turing e um número binário positivo
que a representa.
56
Descrição da Linguagem Ld
Seja uma matriz w bidimensional de números binários onde cada elemento wm,n de w é definido da seguinte
forma:
1 : Se a i-ésima Máquina aceita a cadeia j
0 : Se i não é descrição de Máquina ( Não está na forma 111d11...11d111 ) ou a
i-ésima máquina rejeita j.
Tomemos Ld Í å* tal que Ld = { i : wi,i = 0 } ; Diagonal da matriz com elementos 0.
; Cadeia de entrada é a própria máquina.
Demonstrando que Ld ∉ LRE
Vamos supor por absurdo que L = L(M) para alguma Máquina de Turing M.
Seja k o número binário (cadeia sobre {0,1}* ) que corresponde a descrição de M.
Vejamos o que ocorre em w quando a cadeia k é fornecida como entrada para M:
Caso 1: k Î Ld
Pela definição de Ld temos que wk,k = 0.
No entanto, pela construção de w temos que Mk ( = M ) rejeita k. Contradição.
Caso 2: k Ï Ld
Pela definição de Ld temos que wk,k = 1
No entanto, pela construção de w temos que Mk rejeita k. Contradição.
Conclusão: Ld Ï LRE
56
57
17Linguagens Recursivas
17.1Definição
Conjunto de todas as linguagens aceitas por Máquinas de Turing que sempre param ( Aceitando ou Não ).
Linguagens Recursivas @ Problemas Decidíveis @ Algoritmos
17.2Propriedades
17.2.1União
Sejam L1 e L2 linguagens recursivas.
Construímos M para aceitar L1 È L2 da seguinte forma:
Simular máquina M1 que aceita L1
Simular máquina M2 que aceita L2
Parar e aceitar sse M1 ou M2 aceitam.
17.2.2Complemento
Para construir uma máquina que aceita L , basta inverter o resultado da máquina que aceita L.
17.2.3Interseção
Basta usar as duas propriedades anteriores (De Morgan)
17.2.4Se L ∈ LRE e L ∈ LRE então L,L ∈ LRC
Dado x Î å* construiremos um Autômato que sempre para assim:
Copia x para fita 2 e para fita 3
Simula alternadamente um movimento da máquina de L (M1) na fita 2 e outro da máquina de L (M2) na fita 3
Como x Î L ou x Î L uma das duas simulações sempre para.
Se M1 parar aceita , se M2 parar rejeita.
Possibilidades para L e L:
· L , L Î LRE ( É L,L Î LRC )
· L ( ou L ) Î LRE e L ( ou L ) Ï LRE
· L e L Ï LRE
17.3Linguagem Universal ∈ LRC e ∉ LRE
Lu = { <M>w : <M> aceita w } ; Linguagem Universal
<M> : Código binário que descreve uma Máquina de Turing.
Demonstração de que Lu Ï LRC
Vamos supor por absurdo que Lu seja recursiva.
Seja A uma Máquina de Turing que sempre para e que aceita Lu
Usaremos A para construir um algoritmo ( Máquina ) B para aceitar Ld ( código representando máquinas de
turing que aceitam seu próprio código como entrada ) que opera assim: ( Redução )
B recebe como entrada uma cadeia k ( Representação de uma Máquina de Turing )
Copia k para outra fita
Dobra k; Fita passa a conter kk
Usa A p/verificar se kk Î Lu. ( Sempre pára, visto que A é algoritmo )
Retorna o resultado de A.
Temos então que Ld Î LRC . Como RC é fechado por complemento, temos que, Ld = Ld Î LRC. Contradição.
17.4Problemas de Decisão
17.4.1Definição
São problemas cuja solução é SIM ou NÃO.
Um problema de decisão P é decidível sse a linguagem Lp que contém todos os códigos de instâncias de P
que representam SIM é recursiva.
17.4.2Técnica básica para mostrar que um problema é Indecidível
·
·
·
·
Construir Linguagem L equivalente ao problema.
Supor por absurdo que é Decidível e que portanto L Î LRC
Tomar a Máquina A que aceita L.
Reduzir a máquina A a uma máquina B que aceita um Linguagem L que sabidamente não pertença a LRC
58
17.4.3Problema Indecidível I: Problema da Parada
Descrição: Determinar se uma M.T. pára ao analisar uma cadeia de entrada que também é dada.
Para responder se este problema é decidível devemos resolver o seguinte problema:
Ly = {#<M>#w : M.T para ao computar sobre w } Î LRC
Vamos supor por absurdo que Ly Î LRC
Seja A a Máquina (Que sempre pára) que aceita Ly.
Reduziremos A a uma Máquina B para aceita Lu ( Linguagem Universal ).
Operação de B:
B recebe como entrada #<M>#w
Executa A sobre #<M>#w ( A sempre para )
Se A pára então
Se A rejeita então
M não pára sobre w \ M não aceita w \ B rejeita
Senão ( A aceita \ M pára )
B simula M sobre w ( Note que M pára )
Se M aceita , B aceita
Se M rejeita , B rejeita
Senão ( A não para )
B também não para e portanto rejeita ( Como tinha que ser )
Temos então que Lu Î LRC \ Contradição.
17.4.4Problema Indecidível II: Problema de Parada com fita branca
Descrição: Determinar se uma M.T, M pára ao computar sobre a fita branca.
Lb = { <M> : M pára ao computar sobre a fita branca }
Vamos supor por absurdo que Lb Î LRC
Seja A a Máquina que aceita Lb
Usaremos A para construir uma Máquina B para aceitar Ly ( Problema da Parada )
Operação de B:
B recebe como entrada #<M>#w
B constrói a descrição de uma nova máquina B' que opera assim:
B' Inicia com a fita vazia
; Máquina B' nunca para aqui
B' Escreve w na fita
; Máquina B' nunca para aqui
B' Simula M na fita.
; Máquina B' pode parar aqui dependendo de M e w
B aciona A sobre o código B'
Se A para então
Se A aceita então
B' para com fita vazia \ M pára com w \ B aceita
Senão ( A rejeita )
B' não para com fita vazia \ M não pára com w \ B rejeita
Senão ( A não para )
B também não pára e portanto rejeita.
Temos então que Ly Î LRC \ Contradição
58
59
18Classificação Geral das Linguagens
∑*
Recursivamente Enumeráveis
( Máquinas de Turing , Gramática 0)
Recursivas
( Máquinas de Turing Determ.)
(Algoritmos)
Livres de Contexto
( Autômatos a Pilha , Gramáticas
livre de Contexto )
Regulares
( FSA
Gramáticas Regulares
NFSA
e-FSA
Expressões Regulares
2-FSA )
0*1*
0n1n
ww
Lu
Ld