Brochures e educação">
Autômatos
Autômatos
Autômatos
SIN132
Autmatos
Contedo
1
1.1
Autmatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1
Descrio Informal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
Denio formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3
1.4
Teoria de Autmatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5
Classe de Autmatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1
1.6
Aplicaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7
Simuladores de autmatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.8
1.9
Referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.10 Softwares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
Denio Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2
Exemplo
2.3
Propriedades de fechamento
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4
2.5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1
2.5.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6
Vantagens e Desvantagens
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.7
Ver tambm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8
Notas e referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9
Bibliograa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1
Explicao intuitiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2
Denio formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3
11
3.4
11
ii
CONTEDO
3.5
Propriedades do AFND- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.6
Implementao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.7
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.8
Aplicao de AFND- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.9
Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.10 Referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.11 Softwares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
14
15
4.1
Operao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.2
Denio formal
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Computaes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
4.2.1
4.3
Exemplo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.4
17
4.5
17
4.6
17
4.7
Softwares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.8
Referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
19
5.1
19
5.2
Histria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5.3
Problemas ALL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5.4
Bibliograa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5.5
Ligaes externas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
Mquina de Turing
21
6.1
Denio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6.1.1
Descrio informal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6.1.2
Denio formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
22
6.2.1
Denies alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.2.2
O estado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.2
6.3
Exemplo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.4
24
6.5
24
6.6
24
6.7
25
6.8
Histria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
6.8.1
25
6.8.2
CONTEDO
6.8.3
26
6.8.4
26
6.8.5
27
Ver tambm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.10 Referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.11 Bibliograa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
27
Autmato
28
7.1
Autmato determinstico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
7.2
Autmatos no-determinsticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
7.3
Condies de aceitao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
7.4
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
7.5
30
7.6
Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
7.7
Leitura complementar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
6.9
iii
Autmato hbrido
31
8.1
Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
8.2
Denio Formal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
8.3
Modelos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
8.4
Referncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
8.5
Bibliograa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
8.6
33
8.6.1
Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
8.6.2
Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
8.6.3
Licena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
Captulo 1
Um exemplo de autmato. O estudo de propriedades matemticas destes autmatos a teoria dos autmatos
Na Cincia da computao terica, teoria dos autmatos o estudo dos objetos matemticos chamados
mquinas abstratas ou autmatos e os problemas computacionais que podem ser resolvidos usando esses objetos.
Autmato vem da palavra grega que signica
ao sem inuncia externa; automtico.
A gura ao lado ilustra uma mquina de estados nitos,
que pertence a uma variedade bem conhecida de autmato. Este autmato consiste em estados (representados na gura por crculos), e transies (representado por
setas). Quando o autmato recebe um smbolo de entrada, ele faz uma transio (ou salto) para outro estado,
de acordo com sua funo de transio (que tem como
entradas o estado atual e o smbolo recente).
Teoria dos autmatos tambm est profundamente relacionada teoria das linguagens formais. Um autmato
uma representao nita de uma linguagem formal que
pode ser um conjunto innito. Autmatos so frequentemente classicados pela classe das linguagens formais
que so capazes de reconhecer.
autmato. H estudos das muitas variaes de autmatos. A principal variante, descrita acima, chamada de
Autmatos Um autmato representado formalmente autmato nito determinstico. Seguem variaes populares da denio dos diferentes componentes de autpor uma 5-tupla (Q,,,q0,F), onde:
matos.
Q um conjunto nito de estados.
um conjunto nito de smbolos, chamado Entrada
de alfabeto do autmato.
(ou g) a funo de transio, isto , : Q
x Q.
q0 o estado inicial, isto , o estado do autmato antes de qualquer entrada ser processada,
onde q0 Q.
F um conjunto de estados de Q (isto , F
Q) chamado de estados de aceitao.
Palavra de entrada Um autmato l uma string nita de
smbolos a1 ,a2 ,...., a , onde a , que chamada de
palavra de entrada. O conjunto de todas as palavras
denotado por *.
Execuo A execuo de um autmato sobre uma palavra de entrada w = a1 ,a2 ,...., a *, uma sequncia de estados q1 ,q2 ,...., q , onde q Q tal que q0 o
estado inicial e q = (q1,a) para 0 < i n. Em outras palavras, no comeo o autmato est no estado
inicial q0 , e ento o autmato l smbolos da palavra
de entrada sequencialmente. Quando o autmato l
o smbolo ai ele pula para o estado q = (q1,a).
Diz-se que qn o estado nal da execuo.
Palavra de aceitao Uma palavra w * aceita pelo
autmato se q F.
Linguagem reconhecida Um autmato pode reconhecer uma linguagem. A linguagem L * reconhecida por um autmato o conjunto de todas as palavras que so aceitas pelo autmato.
Linguagens reconhecveis As linguagens reconhecveis so o conjunto de linguagens que so reconhecidas por algum autmato. Para a denio
acima de autmatos, as linguagens reconhecveis so
linguagens regulares. Para diferentes denies de
autmatos, a denio de linguagens reconhecveis
diferente.
No-Determinismo: Um autmato que, aps ler Teoria dos autmatos tambm estuda se existe algum alum smbolo de entrada, pode pular para qual- goritmo efetivo ou no para resolver problemas semequer estado, decidido por sua relao de transi- lhantes seguinte lista:
o. Note que o termo funo de transio substitudo por relao de transio: O autmato no Um autmato aceita alguma palavra de entrada?
determinsticamente decide pular para uma das op(vericao de vazio vacuidade)
es permitidas. Este autmato chamado de autmato no-determinstico.
possvel transformar um dado autmato nodeterminstico em um autmato determinstico sem
Alternamento: Esta ideia muito semelhante ao
mudar a linguagem reconhecvel? (determinizao)
autmato rvore, mas ortogonal. O autmato pode
Para uma dada linguagem formal, qual o menor
executar suas cpias mltiplas sobre o mesmo smautmato que a reconhece? (minimizao).
bolo a ser lido. Este autmato chamado de
autmato nito alternado. A condio de aceitao
deve satisfazer todas as execues de tais cpias para
aceitar a entrada.
1.5 Classe de Autmatos
Condio de aceitao
Certos autmatos so fechados sobre a unio, interseo ou complemento de linguagens formais? (proSimuladores de autmatos so ferramentas pedaggicas
priedades de fechamento)
usadas para ensinar, aprender e pesquisar teoria dos aut Quo expressivo um tipo de autmato em ter- matos. Um simulador de autmato tem como entrada a
mos de reconhecer classe de linguagens formais? E, descrio de um autmato e ento simula seu funcionaquanto ao poder relativo de expressividade? (hie- mento para uma string arbitrria como entrada. A descrirarquia de linguagem)
o do autmato pode ser inserida de vrias formas. Um
4
autmato pode ser denido por uma linguagem simblica
ou sua especicao pode ser inserida em uma forma predenida ou seu diagrama de transio pode ser projetado
no clicar e arrastar do mouse. Simuladores de autmatos
bem conhecidos incluem Turings World, JFLAP, VAS,
TAGS e SimStudio.[1]
1.9 Referncias
John E. Hopcroft, Rajeev Motwani, Jerey D. Ullman
Introduo Teoria de Autmatos, Linguagens e Computao (2 Edio).
[1] Chakraborty, P., Saxena, P. C., Katti, C.
P. 2011.
Fifty Years of Automata Simulation:
A Review.
ACM Inroads, 2(4):5970.
http://dl.acm.org/citation.cfm?id=2038893&dl=ACM&
coll=DL&CFID=65021406&CFTOKEN=86634854
John E. Hopcroft, Rajeev Motwani, Jerey D. Ullman. Introduction to Automata Theory, Languages,
and Computation (2nd Edition). [S.l.]: Pearson Education, 2000. ISBN 0-201-44124-1
Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. ISBN 0534-94728-X Part One: Automata and Languages,
chapters 12, pp. 29122. Section 4.1: Decidable
Languages, pp. 152159. Section 5.1: Undecidable
Problems from Language Theory, pp. 172183.
James P. Schmeiser, David T. Barnard. Producing a
top-down parse order with bottom-up parsing. [S.l.]:
Elsevier North-Holland, 1995.
1.10 Softwares
SCTMF - Software para Criao e Teste de Modelos
Formais.
JFlap - Software americano para testes com interface grca.
Auger - Ambiente para construo e simulao de
autmatos nitos.
Simulador de Automatos - O Simulador de Autmatos uma ferramenta para a criao, simulao
e converso de modelos formais, desenvolvida com
o objetivo de auxiliar o aprendizado de Linguagens
Formais e Autmatos.
Captulo 2
1
0
S0
S2
S1
1
vido seu fator determinstico, ele pode ser implementado atravs de Hardware e Software para resolver diversos problemas especcos. Por instncia, DFAs so utilizados para modelar softwares que validam entradas de
usurio tal como o seu e-mail em um servidor de correio
eletrnico. [4]
aceita w se somente se o ltimo smbolo da entrada leva o "*" uma Kleene star, e.g., 1* indica que h uma ocorautmato a parar em um estado f tal que f F. Caso con- rncia no-negativa de 1s nesse trecho da expresso.
trrio, diz-se que a mquina rejeita a entrada. O conjunto
de cadeias que M aceita chamado Linguagem reconhecida por M e simbolicamente representado por L(M).
2.3 Propriedades de fechamento
Um autmato nito determinstico que no possui estado
inicial ou estados de aceitao conhecido como um Sis- AFDs so fechadas sob as seguintes operaes (o que imtema de Transies ou Semiautmato.
plica que se uma linguagem for obtida atravs da aplicaPara uma melhor compreenso introdutria denio o de uma dessas funes sobre uma ou mais linguagens,
existe uma AFD que reconhece a linguagem resultante):
formal de autmatos, veja Teoria dos autmatos.
2.2 Exemplo
O exemplo a seguir representa um AFD M, com um alfabeto binrio, que requer que sua entrada contenha um
nmero par de 0s.
Unio
Interceo
Concatenao
Negao
Estrela
Quociente
Substituio
Homomorsmo
Sendo AFDs equivalentes a Autmatos nitos no determinsticos (AFN), essas operaes de fechamento podem
ser provadas atravs do uso das propriedades dos AFNs.
M = (Q, , , q0 , F) onde
Q = {S 1 , S 2 },
= {0, 1},
q0 = S 1 ,
F = {S 1 }, e
denido da pela seguinte Tabela de transio de
estados:
O estado S 1 indica que houve um nmero par de ocorrncias do smbolo 0 at ento na entrada, enquanto que S 2
signica que esse valor foi impar. Um 1 na entrada no
altera o estado atual do autmato. Quando a entrada
completamente lida, o estado atual vai indicar se a cadeia
de entrada possui um nmero par de 0s ou no. Caso a cadeia possua de fato uma quantidade par, M vai encerrarse no estado S 1 , um estado de aceitao, tal que a entrada
vai ser aceita. Caso contrrio, se o autmato encontrar-se
no estado S 2 , a mquina rejeita a cadeia.
AFD
De forma a provar a equivalncia entre AFDs e expresses regulares, preciso demonstrar que possvel con- Para concluir a prova de que expresses regulares e AFDs
verter um AFD em uma expresso regular e que tambm descrevem a mesma classe de linguagens (as linguagens
possvel converter uma expresso regular em um AFD. regulares), uma vez mostrado que um AFD pode ser conO procedimento que converte autmatos nitos deter- vertido em uma expresso regular, agora mostrado que
minsticos utiliza outro tipo de autmato, denominado uma expresso regular pode ser convertida em um AFD.
autmato nito no determinstico generalizado. O pro- Fazemos isso convertendo uma expresso regular qualcedimento constitudo em duas etapas, a converso de quer para um autmato nito no determinstico (AFN),
autmato nito determinstico para um autmato nito uma vez que esse tipo de autmato tambm reconhece a
no determinstico generalizado (AFNG), e enm, de um classe de linguagens regulares (e por sua vez, descreve a
AFNG para uma expresso regular. Um AFNG extre- mesma classe que os AFDs).
mamente semelhante a um autmato nito no determinstico (AFN), no entanto, a diferena consiste principalmente em que o AFNG capaz de ler blocos de smbolos
de entrada, ao invs de apenas um nico smbolo de entrada. A funo de transio de um AFNG caracteriza-se
da seguinte forma:
: (Q {qaceita }) (Q {qinicio }) R
De tal forma que:
Q o conjunto de estados;
Seja uma expresso regular R que descreve uma determinada linguagem L . Descrevemos seis casos a serem
tratados na converso para um autmato determinstico.
Caso 1: R = a para algum a .
Ento, L(R) = a . Descrevemos formalmente o seguinte
AFN N tal que L(N ) = R :
N = ({q1 , q2 }, , , q1 , {q2 }) , de forma que a funo de
transio descrita com as transies: (q1 , a) = {q2 } e
(r, b) = para r = q1 ou b = a .
Caso 2: R =
Caso 3: R = .
Q = {q0 } Q1
F = F1 {q0 }
Caso 4: R = R1 R2
Sejam os AFN N1 = (Q1 , , 1 , q1 , F1 ) e N2 =
(Q2 , , 2 , q2 , F2 ) que reconhecem respectivamente as
linguagens descritas por R1 e R2 . O seguinte AFN
N = (Q, , , q0 , F ) reconhece R1 R2 :
Q = {q0 } Q1 Q2
F = F1 F2
1 (q, a)
2 (q, a)
=
{q1 , q2 }
q
q
q
q
Q1
Q2
= q0 a =
= q0 a =
1 (q, a)
1 (q, a)
= 1 (q, a) {q1 }
{q1 }
q
q
q
q
q
/ F1 q Q1
F1 a =
F1 a =
= q0 a =
= q0 a =
(q, a)
q F1 a =
partir de um AFN equivale ao conjunto das partes dos
1
=
(q,
a)
{q
}
q
a
=
1
2
1
2 (q, a)
q Q2
Por outro lado, autmatos de estado nito de potncia
so estritamente limitados nas linguagens que podem reO estado inicial de N o estado inicial de N1 . Os estados conhecer. Muitas linguagens simples, incluindo qualquer
de N so compostos de todos os estados que esto conti- problema que requeira mais que espao constante para
dos no conjunto de estados de N2 ou N1 . Alm disso, os resolver, no podem ser reconhecidos por um AFD. O
estados de aceitao de N so apenas os estados de acei- exemplo clssico de uma linguagem simplesmente destao de N2 . Esse autmato construdo aceita as cadeias crita que nenhum AFD reconhece a linguagem de colque possam ser divididas em duas partes de forma que a chetes, ou seja, linguagem que consiste em colchetes deprimeira parte seja aceita por N1 e a segunda por N2 . vidamente emparelhados como a palavra "(()())". NeEssa construo tambm a prova de que as linguagens nhum DFA pode reconhecer a linguagem de colchetes
regulares so fechadas sob a operao de concatenao. porque no h um limite para a recursividade, ou seja,
sempre se pode incorporar outro par de suportes dentro.
Caso 6: R = R1
Seria necessria uma quantidade innita de estados para
Seja o AFN N1 = (Q1 , , 1 , q1 = 0, F1 ) que reco- reconhec-la. Outro exemplo mais simples a linguagem
nhece a linguagem descrita por R1 . O seguinte AFN consistindo de cadeias de smbolos da forma an bn um
nmero nito de as, seguido por um nmero igual de bs.
N = (Q, , , q, F ) reconhece R1 :
Caso 5: R = R1 R2
2.9 Bibliograa
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.. In: John E.. Introduction to Automata
Theory, Languages, and Computation. 2 ed. [S.l.]:
Addison Wesley, 2001. ISBN 0-201-44124-1 Pgina
visitada em 19 November 2012.
Lawson, Mark V.. Finite automata. [S.l.]: Chapman and Hall/CRC, 2004. ISBN 1-58488-255-7
(1943) A logical calculus of the ideas imminent in
nervous activity. Bulletin of Mathematical Biophysics: 541544.
(1959) Finite automata and their decision problems.. IBM J. Res. Develop.: 114125.
Sakarovitch, Jacques. Elements of automata theory.
Cambridge: Cambridge University Press, 2009.
ISBN 978-0-521-84425-3
Sipser, Michael. Introduction to the Theory of Computation. Boston: PWS, 1997. ISBN 0-534-94728-X.
Section 1.1: Finite Automata, pp. 3147. Subsection Decidable Problems Concerning Regular Languages of section 4.1: Decidable Languages, pp.
152155.4.4 DFA can accept only regular language
Captulo 3
11
3. rn F .
E({p}) = {q Q : pq}
Para qualquer subconjunto P Q , dene-se o fecho-
de P como
E({p})
AFND a linguagem que o AFND aceita. Esta lingua- E(P ) =
pP
gem deve ser uma linguagem regular.
Para todo AFND pode ser encontrada um AFD que aceite
a mesma linguagem. Portanto, possvel converter um
AFND existente em um AFD com o propsito de implementar (talvez) uma mquina mais simples. Isto pode ser
realizado usando a construo do conjunto das partes, o
que pode levar a um aumento exponencial no nmero de
estados necessrios. Uma prova formal desta construo
do conjunto das partes pode ser encontrada aqui (em ingls).
As transies so transitivas, de modo que pode ser demonstrado que, para todo q0 , q1 , q2 Q e P Q , se
q1 E({q0 }) e q2 E({q1 }) , ento q2 E({q0 }) .
Igualmente, se q1 E(P ) e q2 E({q1 }) ento q2
E(P )
Seja x uma cadeia sobre o alfabeto {} . Um AFND M aceita a cadeia x se existe tanto uma representao
de x na forma x1 x2 ...xn , onde xi { } , como
uma sequncia de estados p0 , p1 , ..., pn , onde pi Q ,
Muitas vezes, pode ser mais fcil construir um AFND do
seguindo as seguintes condies:
que um AFD equivalente, tanto pelo entendimento como
pelo tamanho da construo. AFNDs so comumente
1. p0 E({q0 }) ;
introduzidos no incio de cursos de informtica terica
para desenvolver a ideia de no-determinismo em mode2. pi+1 E((pi , xi+1 )) para i = 0, 1, ..., n 1 ;
los computacionais mais poderosos, como as mquina de
Turing.
3. pn F .
12
3.6 Implementao
Existem vrias maneiras de implementar um AFND:
Converter para o AFD equivalente. Em alguns casos isso pode causar um aumento exponencial no tamanho do autmato e, assim, espao proporcional
auxiliar ao nmero de estados do AFND (como o
armazenamento do estado exige no mximo um bit
para cada estado no AFND).
Manter uma estrutura do conjunto de dados de todos os estados em que a mquina poderia estar. Na
leitura do ultimo simbolo de entrada, se um desses
estados um estado nal, a mquina aceita a cadeia. No pior dos casos, isso pode exigir espao auxiliar proporcional ao nmero de estados do AFND;
se a estrutura de conjunto usa um bit por estado do
AFND, ento esta soluo exatamente equivalente
a anterior.
Explicitamente propague tokens atravs da estrutura de transio do AFND e combine sempre que
um token alcanar um estado nal. Isto, s vezes, til quando o AFND pode codicar contextos adicionais sobre os eventos que desencadearam da transio. (Para uma implementao que
usa esta tcnica acompanhe as referncias e olhe os
Tracematches.[3] )
3.7 Exemplo
Exemplo 1: O seguinte exemplo explica um AFND
M, com um alfabeto binrio, que determina se uma
entrada contm um nmero par de 0s ou um nmero
par de 1s (Note que 0 ocorrncias um nmero para
de occorrncias). Seja M= (Q, , T, s0 , F) onde
= {0, 1},
Q= {s0 , s1 , s2 , s3 , s4 },
2
1
aceita a dada cadeira. Isso tambm requer armazenamento linear com respeito ao nmero de estados
do AFND, como tambm pode haver uma mquina
para cada estado do AFND. Dessa forma, pode-se
pensar no no-determinismo dos AFNDs como uma
0
computao paralela, na qual o AFND (anlogo a
0
0
1
um processo) pode se bifurcar (de forma anloga
chamada de sistema Fork).
4
3
rvore de possibilidades. Derivada da ideia de ramos de computao, nessa forma, representamos a
computao a partir de uma rvore de possibilida1
des cuja raiz corresponde ao incio da computao. :
A cada smbolo de entrada lido, analisa-se a transio e se criam ns lhos adequadamente, isto , M pode ser visto como a unio de dois AFDs: um com
caso haja 2 estados possveis em uma dada transi- os estados {S 1 , S 2 } e o outro com os estados {S 3 , S 4 }.
o, a rvore ramica no nvel atual e criam-se 2
renovos lhos. Analogamente, se houver apenas uma A linguagem de M pode ser descrita pela linguagem
gular
dada
por
esta
expresso
regular
(1
(01
01
)
)
(0
(10
10
)
)
.
momento e se no houver transio possvel, o ramo
morre e no mais levado em conta na computa Exemplo 2:
o.
3.9. NOTAS
Criar o diagrama do AFND da linguagem L = {w | w termina em 00} com 3 estados. Resposta: O estado inicial
de no aceitao e ca em loop recebendo 1s e 0s at
que ele adivinha de forma no determinstica que um 0
recebido o penltimo 0 da cadeia, e assim, passa para
o segundo estado, que por sua vez, recebe o ltimo zero
e passa para o estado nal de aceitao, que no tem nenhuma transio partindo dele, e caso recebe um outro
smbolo, o ramo da computao morre.
(Exemplo de exercco no resolvido do Sipser).
Exemplo 3:
Criar o diagrama do AFND da linguagem U = { w | w 0*
} com 1 estado. Resposta: O estado inicial o estado de
aceitao e tem apenas 1 transio, que para ele mesmo,
no caso de ler o smbolo 0 da entrada. Caso outro smbolo
seja lido, o ramo da computao morre. Neste caso, o no
determinismo est associado a no ter uma transio para
todos os smbolos do alfabeto. Fazendo um comparativo
com o AFD, seria necessrio criar um outro estado que
alcanado caso o estado inicial leia 1 da entrada, e que
possui um loop para ele mesmo ao receber 0s e 1s.
(Exemplo de exerccio no resolvido do Sipser).
Exemplo 4:
Criar do diagrama do AFND da linguagem A = { w | w =
{0}} com 2 estados. Resposta: O estado inicial estado
de no aceitao e tem uma transio para o estado nal
de aceitao ao ler o smbolo 0 da entrada. O estado nal
de aceitao no possui transies para nenhum outro estado. Caso o estado inicial leia o smbolo 1 da entrada ou
o estado nal ler 0 ou 1, o ramo da computao morre.
13
matemtico necessrio para estabelecer muitas propriedades importantes na teoria da computao. Por exemplo, muito mais fcil provar as propriedades que seguem
usando AFNDs do que AFDs:
A unio de duas linguagens regulares regular:
A ideia da prova parte do princpio de que, tendo duas
linguagens regulares e os AFNDs que as reconhecem, podemos tomar os dois AFNDs e combin-los com um terceiro AFND que aceita sua entrada de qualquer um dos
dois AFNDs prvios a aceita. A prova formal pode ser
encontrada aqui.
A concatenao de duas linguagens regulares regular:
Sendo dois AFNDs iniciais A1 e A2 , a ideia da prova
consiste em construir um novo AFND Aconcat usando a
estrutura de A1 e A2 na construo. O novo AFND possui como estado inicial, o estado inicial do AFND A1 e
possui toda a estrutura de A1 , com os estados de aceitao de A1 transformados em estados de no-aceitao
possuidores de transies para o estado inicial de A2 .
O novo AFND, por conseguinte, tambm possui toda a
estrutura de A2 , e seus estados de aceitao so os mesmos de A2 . Dessa forma, a entrada sempre poder ser
quebrada em duas partes no-deterministicamente, e s
ser aceita se puder ter a primeira parte aceita por A1 e a
segunda por A2 .
O Fecho de Kleene de uma linguagem regular regular:
3.9 Notas
[1] Rabin and Scott (1959)
[2] FOLDOC Free Online Dictionary of Computing, Finite
State Machine
14
3.10 Referncias
M. O. Rabin and D. Scott, Finite Automata and
their Decision Problems, IBM Journal of Research
and Development, 3:2 (1959) pp. 115125.
Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728X. (see section 1.2: Nondeterminism, pp.4763.)
John E. Hopcroft and Jerey D. Ullman,
Introduction to Automata Theory, Languages,
and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X.
(ver captulo 2)
Martin, John C. - Introduction to languages and the
theory of computation (2 Edio)
3.11 Softwares
Auger - Software brasileiro com interface grca
para construo e simulao de autmatos nitos e
converso para outros modelos formais.
Simulador de Autmatos - Software para criao,
teste e converso de Modelos Formais. Com interface grca.
SCTMF - Software para Criao e Teste de Modelos
Formais.
JFlap - Software americano para testes com interface grca.
Captulo 4
4.1 Operao
M = (Q, , , , q0 , F )
16
4.3 Exemplo
Um passo do autmato com pilha.
que ainda no foi lida e o contedo da memria (o cabealho escrito primeiro). A funo de transio dene a relao origina M de M na descrio instantnea
(ID). Para instrues (p, a, A, q, ) existe um passo
(p, ax, A) M (q, x, ) , para todo x e todo
.
Em geral, autmatos com pilha so no determinsticos, o que signica dizer que dada uma descrio instantnea (p, w, ) podem haver diversos passos possveis. Qualquer um desses passos pode ser escolhido dun n
rante uma computao. Com a denio acima, em cada AP para {0 1 | n 0} (por estado nal).
passo um smbolo nico (localizado no topo da pilha)
retirado e substitudo por quantos smbolos forem ne- M = (Q, , , , p, Z, F ) , onde
cessrio. Como consequncia, nenhum passo denido
Q = {p, q, r}
quando a pilha est vazia.
Computaes dos autmatos com pilha so sequncias de = {0, 1}
passos. A computao comea no estado inicial q0 com o = {A, Z}
smbolo inicial da pilha Z na pilha e uma cadeia w na ta
de entrada e, portanto, com a descrio inicial (q0 , w, Z) F = {r}
. H duas maneiras de aceitar: O autmato com pilha consiste nas seis instrues seguintes:
aceita tanto por estado nal, o que signica que depois de
(p, 0, Z, p, AZ) , (p, 0, A, p, AA) , (p, , Z, q, Z) ,
ler sua entrada, o autmato atinge um estado de aceitao
(p, , A, q, A) , (q, 1, A, q, ) , e (q, , Z, r, Z) .
(in F ), quanto por pilha vazia ( ), o que signica que
aps ler a cadeia de entrada, o autmato esvazia sua pilha. Ou seja, no estado p para cada smbolo 0 que for lido, um
O primeiro modo de aceitao usa a memria interna, os A colocado na pilha. Empilhar um smbolo A no topo
de um outro A formalizado como trocar o smbolo A
estados, e o segundo modo a memria externa, a pilha.
por AA . No estado q , para cada smbolo 1 lido, um A
Denio formal:
a desempilhado. Em um outro momento, o autmato
se move do estado p para o estado q , enquanto ele pode
1. L(M ) = {w |(q0 , w, Z) M (f, , ) com mover do estado q para o estado de aceitao r somente
quando a pilha possuir um nico Z .
f F e } (Estado nal)
Representamos a instruo (p, a, A, q, ) como uma
2. N (M ) = {w |(q0 , w, Z) M (q, , ) com ponte que sai do estado p para o estado q rotulada por
q Q} (Pilha vazia)
a; A/ (leia a ; substitui A por ).
17
e substitui-la pelo lado direito de uma regra gramatical.
Onde a gramtica gera um smbolo terminal, o PDA l
um smbolo de entrada quando o smbolo mais alto na
pilha. De certa forma, a pilha do PDA contm os dados no transformados da gramtica, correspondente a
um percurso pr-ordem de uma rvore de derivao.
Tecnicamente, dada uma gramtica livre de contexto, o
AP construdo da seguinte forma:
1. (1, , A, 1, ) para cada regra A (expand)
A seguir ilustramos como o AP acima computa sobre diComo resultado, obtemos um autmato com pilha de um
ferentes cadeias de entrada.
nico estado. O estado aqui 1 , aceitando a linguagem
(a) Cadeia de entrada = 0011. H vrias computaes, livre de contexto por pilha vazia. O smbolo inicial da
dependendo do momento em que feita a mudana do pilha igual ao axioma da gramtica livre do contexto.
estado p para o estado q . Apenas uma dessas computaO inverso, encontrar uma gramtica para um AP dado,
es aceita.
no to simples. O truque codicar dois estados do
AP em smbolos no-terminais da gramtica.
(p, 0011, Z) (q, 0011, Z) (r, 0011, Z)
(p, 0011, Z) (p, 011, AZ) (q, 011, AZ)
(iii) (p, 0011, Z)
Teorema Para cada autmato com pilha M possvel construir uma gramtica livre do contexto G tal que
N (M ) = L(G) .
M = (Q, , , , q0 , F )
onde Q, , , q0 e F so denidos da mesma forma que
um AP.
: Q P (Q )
a funo de transio.
Regras de computao para um APG so as mesmas que
para AP, exceto que a's e b's so agora cadeias ao
invs de smbolos.
APGs e APs so equivalentes, ou seja, se uma linguagem
reconhecida por um AP, ela tambm reconhecida por
um APG, e vice-versa.
Podemos formular uma prova analtica da equivalncia
entre APGs e APs usando a seguinte simulao:
Faa (q1 , w, x1 x2 ...x ) (q2 , y1 y2 ...y ) ser uma transio do APG
18
Onde q1 , q2 Q , w , x1 , x2 , . . . , xm ,
m 0 , y1 , y2 , . . . , yn , n 0 .
Construa as seguintes transies para o AP:
(q1 , w, x1 ) (p1 , )
(p1 , , x2 ) (p2 , )
..
.
(p -, , x ) (p , )
(p , , ) (p , y )
(p , , ) (p , y -)
..
.
(p -, , ) (q2 , y1 )
4.7 Softwares
Simulador de Autmatos- Software para criao,
teste e converso de Modelos Formais. Com interface grca.
SCTMF- Software para Criao e Teste de Modelos
Formais.
JFlap- Software americano para testes com interface
grca.
4.8 Referncias
Michael Sipser. Introduo Teoria da Computao. Traduo brasileira de Introduction to the
Theory of Computation (PWS Publishing Company, 2nd edition, 2005), por Ruy de Queiroz, reviso Newton Vieira, Cengarle Learning, 2007 ISBN
978-85-221-0499-4.
Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, SpringerVerlag, 1997, 111-174.
Captulo 5
para direita. Como tem carter no determinstico os estados podem ter mais de uma sada com o mesmo smbolo, quando isso ocorre uma cpia do ALL criada e
executada simultaneamente, a primeira cpia que parar
em um estado nal aceita, e as outras so excludas.
A transio representada por (smbolo lido, smbolo a
ser escrito, direo para qual o cabeote de leitura/escrita
deve ir).
Uma caracterstica importante dos ALLs que um ALL
pode ter somente um nmero limitado de conguraes
dado que a entrada tem tamanho n.
Dado que a entrada tem tamanho n, seja M um ALL com
q estados e s smbolos no alfabeto da ta ento podemos dizer que existem exatamente q*n*s^n conguraes distintas de M.
5.2 Histria
Em 1960, Myhill introduziu um modelo de autmato hoje
conhecida como autmato linearmente limitado determinstico. [1] Pouco depois, Landweber provou que as linguagens aceitas por um ALL determinstico so sempre
19
20
5.4 Bibliograa
COHEN, D. I. A. Introduction to Computer Theory.
New York: John Wiley & Sons, 1997.
MENEZES, P. B. Linguagens Formais e Autmatos.
Porto Alegre: Sagra Luzzatto, 2005.
VIEIRA, N. J. Introduo aos Fundamentos da
Computao - Linguagens e Mquinas. So Paulo:
Pioneira Thomson e Learning, 2006.
Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.
John Myhill: Linearly Bounded Automata, WADD
Technical Note 60-165, Wright-Patterson Air Force
Base, Wright Air Development Division, Ohio, junho 1960.
Captulo 6
Mquina de Turing
2. Um cabeote, que pode ler e escrever smbolos na
ta e mover-se para a esquerda e para a direita.
3. Um registrador de estados, que armazena o estado da
mquina de Turing. O nmero de estados diferentes
sempre nito e h um estado especial denominado
estado inicial com o qual o registrador de estado
inicializado.
Representao artstica de uma mquina de Turing
A mquina de Turing um dispositivo terico conhecido como mquina mundial, que foi concebido pelo
matemtico britnico Alan Turing (1912-1954), muitos
anos antes de existirem os modernos computadores digitais (o artigo de referncia foi publicado em 1936). Num
sentido preciso, um modelo abstrato de um computador,
que se restringe apenas aos aspectos lgicos do seu funcionamento (memria, estados e transies) e no sua Note que cada parte da mquina nita; sua quantidade
implementao fsica. Numa mquina de Turing pode-se de ta potencialmente ilimitada que d uma quantidade
modelar qualquer computador digital.
ilimitada de espao de armazenamento.
Turing tambm se envolveu na construo de mquinas
fsicas para quebrar os cdigos secretos das comunicaes alems durante a II Guerra Mundial, tendo utilizado 6.1.2 Denio formal
alguns dos conceitos tericos desenvolvidos para o seu
Mquina de Turing com uma ta
Mais formodelo de computador universal.
malmente, uma mquina de Turing (com uma ta)
usualmente denida como uma Tupla M
=
(Q, , , s, b, F, ) , onde
6.1 Denio
6.1.1
Descrio informal
s Q o estado inicial
b o smbolo branco (o nico smbolo que
se permite ocorrer na ta innitamente em qualquer
passo durante a computao)
F Q o conjunto dos estados nais
: Q Q {, } uma funo parcial chamada funo de transio, onde o movimento para a esquerda e o movimento para a
direita.
22
Denies na literatura s vezes diferem um pouco, para
tornar argumentos ou provas mais fceis ou mais claras,
mas isto sempre feito de maneira que a mquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto {, } para {, , P } , onde
P permite ao cabeote permanecer na mesma clula da
ta em vez de mover-se para a esquerda ou direita, no
aumenta o poder computacional da mquina (Fonte - Michael Sipser - Int Teoria da Computao).
Mquina de Turing com k tas Uma mquina de Turing com k tas tambm pode ser descrita como uma 7upla M = (Q, , 1 , 2 , ..., k , s, b, F, ) , onde
Q um conjunto nito de estados
Outros autores (Minsky (1967) p. 119, Hopcroft e UllNas palavras de Van Emde Boas (1990), p. 6: O objeto man (1979) p. 158, Stone (1972) p. 9) adotam uma condo conjunto terico [sua descrio formal sete-tupla si- veno diferente, com um novo estado q listado imedimilar ao acima] fornece apenas informao parcial sobre atamente depois do smbolo escaneado S :
como a mquina agir e com o que suas computaes se
parecero.
(denio 2): (q, S , q , S /E/N, L/R/N)
Por exemplo,
( estado atual q , smbolo escaneado S , novo estado q , smbolo
Sero necessrias muitas decises sobre com o que
de impresso S /apagar E/nada N
os smbolos realmente se parecem, e uma forma de
, move_um_quadrado_da_ta escontra-prova de smbolos de escrita e leitura indequerda L/direita R/nada N )
nidamente.
As operaes shift left e shift right podem deslocar
a cabea da ta sobre a ta, mas quando realmente
construir uma mquina de Turing, isso mais prtico para fazer a ta deslizar para frente e para trs
sob a cabea em vez disso.
6.3. EXEMPLO
N2, N3 (cf Turing em Undecidable, p. 126). Ele permitiu a rasura do quadrado escaneado nomeando o 0th
smbolo S0 = apagar ou branco, etc. Entretanto, ele
no permitiu a no impresso, ento toda linha de instruo inclui smbolo de impresso S " ou apagar (cf nota
de rodap 12 em Post (1947), Undecidable p. 300). As
abreviaes so de Turing(Undecidable p. 119). Posteriormente ao paper original de Turing em 19361937, os
modelos de mquina tm permitido todos os nove tipos
possveis de 5-tuplas:
23
composto a descrio instantnea e segue a convenso
de Turing de colocar o estado atual (rtulo-instruo,
m-congurao) para a esquerda do smbolo escaneado
(p. 149).
Exemplo: estado total do problema do castor ocupado de 3 estados e 2 smbolos aps 3 movimentos
(pegando de exemplo run na gura abaixo):
1A1
Est. Smb. Smb. Est. Act. Lido Escr. Mv. Novo -------- ----- --- ---- s1 1 s2 s2 1 1 s2 s2 s3 s3
1 s4 s3 1 1 s3 s4 1 1 s4 s4 s5 s5 1 1
s5 s5 1 s1
A primeira linha desta tabela pode ser lida como: Se a
mquina estiver no estado s1 e o smbolo lido pelo cabeote for 1, ento escreva o smbolo , mova uma posio
para a direita e mude o estado para s2.
Uma computao nesta mquina de Turing pode ser, por
exemplo: (a posio do cabeote indicada mostrando-se
a clula em negrito)
Passo Estado Fita ----- ------ ---------- 1 s1 11 2 s2 1 3
s2 1 4 s3 1 5 s4 11 6 s5 11 7 s5 11 8 s1
111 9 s2 11 10 s3 11 11 s3 11 12 s4 111
13 s4 111 14 s5 111 15 s1 1111
O comportamento desta mquina pode ser descrito como
um lao (loop): Ele inicia em s1, substitui o primeiro 1
24
com um , ento usa o s2 para mover para a direita, passando pelos 1s e pelo primeiro encontrado. S3 ento
passa pela prxima seqncia de 1s (inicialmente h nenhuma) e substitui o primeiro que encontra por um 1.
S4 move de volta para a esquerda, passando pelos 1s at
encontrar um e vai para o estado s5. S5 ento move para
a esquerda, passando pelos 1s at achar o que foi originalmente escrito por s1. Ele substitui o por 1, move
uma posio para a direita e entra no estado s1 novamente
para outra execuo do lao. Isso continua at s1 achar
um (este o que ca entre as duas cadeias de 1s),
situao na qual a mquina pra.
6.8. HISTRIA
Outra limitao de mquinas de Turing que elas no
modelam a organizao estrita de um problema especco. Por exemplo, computadores modernos so na verdade instncias de uma forma mais especca de mquina
de computao, conhecido como mquina de acesso aleatrio. A principal diferena entre esta mquina e a mquina de Turing que esta utiliza uma ta innita, enquanto a mquina de acesso aleatrio utiliza uma sequncia indexada numericamente (tipicamente um campo inteiro). O resultado desta distino que h otimizaes
computacionais que podem ser executadas baseadas nos
ndices em memria, o que no possvel numa mquina
de Turing geral. Assim, quando mquinas de Turing so
utilizadas como base para tempo de execues restritos,
um falso limite inferior pode ser provado em determinados tempos de execuo de algoritmos (graas premissa falsa de simplicao da mquina de Turing). Um
exemplo disto uma ordenao por contagem, o que
aparentemente viola o limite inferior theta(n log n) em
algoritmos de ordenao.
25
No difcil simular uma mquina de Turing num computador moderno (exceptuando pela quantidade de memria limitada existente nos computadores actuais). O
site de busca Google, em comemorao aos 100 anos de
Alan Turing, publicou um doodle dia 23 de junho de
2012, em forma de uma mquina de Turing.[1]
Gandy arma que as funes que podem ser calculadas por (1), (2), e (4) so precisamente as que so
Turing computveis . " (p. 53). Ele cita outras propostas de mquinas de calcular universais includas
as de Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Cougnal
possvel construir uma mquina de Turing com base pu(1933), Vannevar Bush (1936), Howard Aiken ( 1937).
ramente mecnica. O matemtico Karl Scherer construiu
No entanto:
essa mquina em 1986, usando conjuntos de construo
de metal, plstico e alguma madeira. A mquina, com 1,5
m de altura, usa puxes de os para ler, movimentar e escrever informao, a qual , por sua vez, representada por
rolamentos. A mquina encontra-se atualmente em exibio na entrada do Departamento de Cincia de Com- 6.8.2 O Entscheidungsproblem (o problema de deciso): O dcimo proputadores da Universidade de Heidelberg, na Alemanha.
O conceito de mquina de Turing foi usado como ferramenta educativa na obra de co cientca The Diamond
Age (1995), escrita por Neal Stephenson. A personagem
principal, Nell, possui um livro interactivo que a ensina
a pensar criativa e logicamente apresentando-lhe puzzles
numa histria, os quais, sendo mquinas de Turing, se tornam cada vez mais complexos medida que a narrativa
se desenvolve. Estes puzzles comeam por ser simples
aparelhos mecnicos e evoluem para processos econmicos abstractos, atingindo um ponto em que se assiste
interao entre completos reinos ccionais.
6.8 Histria
26
6.8.3
Alan
Turing
automtica)
6.11. BIBLIOGRAFIA
e Marvin Minsky reduziram a mquina de Turing a uma
forma mais simples (um precursor da mquina de PostTuring de Martin Davis); simultaneamente pesquisadores europeus estavam reduzindo o novssimo computador
eletrnico a um computador como objeto terico equivalente ao que estava sendo chamado de mquina de Turing. No nal dos anos 1950 e incio dos anos 1960,
os desenvolvimentos, coincidentemente paralelamente,
Melzak e Lambek (1961), Minsky (1961), e Shepherdson e Sturgis (1961) continuaram o trabalho europeu e
reduziram a mquina de Turing para uma mquina mais
amigvel, como um computador de modelo abstrato chamado de counter machine ; Elgot e Robinson (1964),
Hartmanis (1971), Cook e Reckhow (1973) levaram este
trabalho ainda mais com a mquina de registo e de acesso
aleatrio mquina modelos, mas basicamente todos so
apenas mquinas multi-ta de Turing com um conjunto
de instrues aritmticas.
6.8.5
Hoje, o contador, registrador e mquinas de acesso aleatrio e seu pai a mquina de Turing continuam a ser os
modelos de escolha para os tericos que investigam questes da teoria da computao . Em particular, a teoria da
complexidade computacional faz uso da mquina de Turing:
Dependendo dos objetos um gosta de manipular os clculos (nmeros como inteiros no negativos ou cordas alfanumricos), dois modelos tm obtido uma posio dominante na teoria da complexidade baseada em mquina:
27
6.11 Bibliograa
Rolf Herken: The Universal Turing Machine - A
Half-Century Survey, Springer Verlag, ISBN 3-21182637-8
Paul Strathern: Turing and the Computer - The
big idea, Anchor Books/Doubleday, ISBN 0-38549243-X
Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings
of the London Mathematical Society, Series 2, Volume 42, 1936; reimpresso em M. David (ed.), The
Undecidable, Hewlett, NY: Raven Press, 1965;
Boolos, G. and Jerey, R., Computability and Logic, 2 ed., Cambridge: Cambridge University Press,
1980.
Rogozhin, Yurii, A Universal Turing Machine with
22 States and 2 Symbols, Romanian Journal Of Information Science and Technology, 1(3), 259-265,
1998. (surveys known results about small universal
Turing machines)
6.10 Referncias
[1] Google. Doodles www.google.com. Visitado em 23 de
junho de 2012.
Captulo 7
Autmato
Na teoria de autmatos, um ramo da teoria da computa Acc a condio de aceitao, formalmente um subo, um autmato uma variao do autmato nito
conjunto de Q
que roda sobre cadeias innitas como entrada, ao invs
de nitas. Uma vez que um -autmato no para, eles Uma entrada para A uma string innita sobre o alfabeto
tm uma variedade de condies de aceitao, em vez de , i.e. uma sequencia innita = (a1 ,a2 ,a3 ,...). A exesimplesmente um conjunto de estados de aceitao.
cuo de A em tal entrada uma sequencia innita =
(r
0 ,r1 ,r2 ,...) de estados, denidos da seguinte forma:
-autmatos so teis para a especicao de comportamento de sistemas que no so esperados para terminar, como hardware, sistemas operacionais e sistemas de
controle. Para tais sistemas, voc pode querer especicar uma propriedade, como para cada pedido, uma conrmao, eventualmente, segue, ou sua negao existe
um pedido que no seguido por uma conrmao. O
ltimo uma propriedade das palavras innitas: nada se
pode dizer de uma sequncia nita que satisfaz esta propriedade.
Classes de -autmatos incluem o autmatos de Bchi,
'Rabin de autmatos, 'autmatos de Streett, 'autmatos
de paridade e Muller autmatos, determinstico ou no
determinstico. Essas classes de -autmatos diferem
apenas em termos de condicionar a aceitao. Todos eles
reconhecem precisamente a linguagens regulares , excepto pelos autmatos do Bchi determinsticos, que so
estritamente mais fracos do que todos os outros. Embora
todos estes tipos de autmatos reconhecem o mesmo conjunto de linguagens , eles ainda diferem em conciso de
representao para uma dada linguagem .
r0 = q0 .
r1 = (r0 ,a1 ).
r2 = (r1 ,a2 ).
...
rn = (rn,an).
A nalidade principal de um autmato denir um
subconjunto do conjunto de todas as entradas: O conjunto de entradas aceitas. Considerando que, no caso de
um simples autmato nito cada corrida termina com um
estado rn e a entrada aceita se e somente se rn um estado de aceitao, a denio do conjunto de entradas
aceitas mais complicado para autmatos . Aqui devemos olhar para a execuo completa de . A entrada
aceita se a execuo correspondente est em Acc. Oconjunto de entradas de palavras aceitas chamado de linguagem reconhecida por um autmato, que denotado
como L(A).
7.2 Autmatos
determinsticos
no-
29
Q um conjunto nito. Os elementos de Q so cha- exemplo, se uma placa de rede recebe pedidos de ping
mados de estados de A.
innitos, ento pode deixar de responder a alguns dos pedidos, mas deve responder a um subconjunto innito de
um conjunto nito chamado de alfabeto de A.
solicitaes de ping recebidas. Isto motiva a seguinte de um subconjunto de Q Q e chamado de nio: Para qualquer execuo , deixe Inf() ser o conjunto de estados que ocorrem frequente e innitamente
relao de transio de A.
em . Esta noo de certos estados a ser visitado innitas
Q0 um subconjunto de Q, conjunto inicial de esta- vezes ser til na denio das condies de aceitao a
dos.
seguir.
Acc a condio de aceitao, um subconjunto de
Q .
Ao contrrio de um autmato determinstico que tem
uma funo de transio , a verso no-determinstica
tem uma transio relao . Note-se que pode ser
considerada como uma funo : Q P(Q) de Q
para o conjunto das partes P(Q). Assim, dado o estado
qn e o smbolo an, o prximo estado qn no necessariamente determinada de forma exclusiva, uma vez que
h um conjunto de estados possveis prximos. A execuo de A sobre a entrada = (a1 ,a2 ,a3 ,...) qualquer
sequencia innita = (r0 ,r1 ,r2 ,...) de estados que satifaz
as seguinte condies
r0 um elemento de Q0 .
r1 um elemento de (r0 ,a1 ).
r2 um elemento de (r1 ,a2 ).
...
rn um elemento de (rn,an).
30
CAPTULO 7. AUTMATO
0
q
0
0
7.6 Referencias
Farwer, Berndt (2002), "-Automata, in Grdel,
Erich; Thomas, Wolfgang; Wilke, Thomas, Automata, Logics, and Innite Games, Lecture Notes in
Computer Science, Springer, pp. 321, ISBN 9783-540-00388-5.
Automata on Innite Words Slides for a tutorial by
Paritosh K. Pandya.
Captulo 8
Autmato hbrido
Na teoria dos autmatos, um autmato hbrido um
modelo matemtico para descrever precisamente sistemas onde processos computacionais digitais interagem
com processos fsicos analgicos. Um autmato hbrido
uma mquina de estados nitos com um conjunto nito
de variveis contnuas, cujos valores so descritos por um
conjunto de equaes diferenciais comuns. Esta especicao combinada de comportamentos discretos e contnuos permite que sistemas dinmicos que compreendem
dois componentes digitais e analgicos a serem modelados e analisados.
8.1 Exemplos
Um exemplo simples o sistema sala-termostatoaquecedor, onde a temperatura da sala evolui de acordo
com duas leis, as da termodinmica, e do estado do aquecedor (ligado / desligado); o termostato julga a temperatura, executa computaes precisas e modica o aquecedor para ligado e desligado. Em geral, os autmatos
hbridos tm sido usados para modelar e analisar uma
grande variedade de sistemas embarcados, incluindo sistemas de controle de veculos, sistemas de controle de
trfego areo, robs mveis, e processos de sistemas da
biologia..
Autmatos hbridos ocorrem de vrias maneiras: o automato hbrido Alur-Henzinger um modelo popular,
que foi desenvolvido primeiramente para a anlise algo8.2 Denio Formal
rtmica do modelo de vericao de sistemas hbridos.
A ferramenta de vericao modelo HyTech baseado
Um autmato hbrido Alur-Henzinger H compreende os nesse modelo. O modelo Autmato Entrada/Sada Hbrido foi desenvolvida mais recentemente. Este modelo
seguintes componentes:[1]
permite a modelagem composicional e a anlise de sistemas hbridos. Outro formalismo que til para imple Um conjunto nito X = {x1 , ..., xn } de variveis
mentaes do modelo dos autmatos hbridos o autde nmeros reais. O nmero n chamado de dimenmato hbrido preguioso linear.
so de H . Faa X ser o conjunto {x 1 , ..., x n } de
variveis pontuais que representam as primeiras derivadas durante a transformao contnua, e faa X
ser o conjunto {x1 , ..., xn } de variveis preparadas 8.4 Referncias
que representam valores na concluso de transformao discreta.
Um multigrafo nito direcionado (V, E) . Os vrtices em V so chamados de modos de controle. As
31
[1] Henzinger, T.A. The Theory of Hybrid Automata. Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science (LICS), pages 278-292, 1996.
32
8.5 Bibliograa
Rajeev Alur, Costas Courcoubetis, Nicolas Halbwachs, Thomas A. Henzinger, Pei-Hsin Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio
Yovine The algorithmic analysis of hybrid systems.
Theoretical Computer Science, volume 138(1), pages 334, 1995.
Nancy Lynch, Roberto Segala, Frits Vaandrager,
Hybrid I/O Automata. Information and Computation, volume 185(1), pages 103157, 2003.
33
Texto
Teoria dos autmatos Fonte: http://pt.wikipedia.org/wiki/Teoria%20dos%20aut%C3%B4matos?oldid=38936301 Contribuidores: LeonardoG, LeonardoRob0t, OS2Warp, Olavom, Ccero, Khullah, Chlewbot, Leonardo.stabile, Njr, Chentz, JAnDbot, Kaktus Kid, Vitor
Mazuco, Maurcio I, Salebot, JotaCartas, Rubinbot, Michelmenega, Dayane C., FMTbot, ChuispastonBot, WikitanvirBot, MerlIwBot,
Leoenciwiki, Legobot e Annimo: 19
Autmatos nitos determinsticos Fonte: http://pt.wikipedia.org/wiki/Aut%C3%B4matos%20finitos%20determin%C3%ADsticos?
oldid=39702024 Contribuidores: LeonardoG, Santana-freitas, Olavom, SallesNeto BR, Leonardo.stabile, Njr, VolkovBot, Luckas-bot, Diego Queiroz, Mobyduck, BenzolBot, Rjbot, ZroBot, Rodrigolopes, Legobot, Mgtmc, Gpp40 e Annimo: 12
Mquina de estados nitos no determinstica Fonte: http://pt.wikipedia.org/wiki/M%C3%A1quina%20de%20estados%20finitos%
20n%C3%A3o%20determin%C3%ADstica?oldid=40404793 Contribuidores: Hgfernan, Obscuro, Jprisco, Fernando S. Aldado, Leonardo.stabile, Njr, He7d3r, Master, Rei-bot, Castelobranco, EuTuga, VolkovBot, LeoBot, Fabiano Tatsch, Eamaral, Salebot, Diego Queiroz, Xqbot, Rjbot, ZroBot, Henrique, Vanessalarize, J. A. S. Ferreira, Addbot, Dhudupires, Vmrc e Annimo: 3
Autmato com pilha Fonte: http://pt.wikipedia.org/wiki/Aut%C3%B4mato%20com%20pilha?oldid=36151100 Contribuidores: Leonardo.stabile, Njr, Reynaldo, TXiKiBoT, ChristianH, Luckas-bot, Ptbotgourou, Diego Queiroz, Mobyduck, Ripchip Bot, ZroBot, KLBot2,
Deboracgcorreia, Kascyo, JYBot e Annimo: 4
Autmato linearmente limitado Fonte: http://pt.wikipedia.org/wiki/Aut%C3%B4mato%20linearmente%20limitado?oldid=34731604
Contribuidores: Master, TXiKiBoT, Fabiano Tatsch, MystBot, Vanthorn, Diego Queiroz, Xqbot, Faustino.F, Michelmenega, QuarkAWB,
Aleph Bot, ZroBot, KLBot2, Jphmf e Annimo: 1
Mquina de Turing Fonte: http://pt.wikipedia.org/wiki/M%C3%A1quina%20de%20Turing?oldid=41343848 Contribuidores: Patrick,
LeonardoG, Muriel Gottrop, Angeloleithold, E2mb0t, Heitor, LeonardoRob0t, Alexg, Rafael.afonso, Campani, Nuno Tavares, NTBot,
Rodrigo Rocha, RobotQuistnix, Leslie, Clara C., OS2Warp, Adailton, Zwobot, Nomad, YurikBot, Ccero, Lus Felipe Braga, Villarinho,
Leonardo.stabile, Njr, Thijs!bot, Escarbot, JAnDbot, Kid A, Ricvelozo, TXiKiBoT, VolkovBot, BOTijo, Kaktus Kid, Lopima, LeoBot,
Marcelopge, Thrasherbermensch, Luckas-bot, Eamaral, Xqbot, RibotBOT, Michelmenega, TobeBot, Rjbot, Arthyole, Ci.cp, EmausBot,
JackieBot, ZroBot, Sygmn, Nelson Teixeira, Stuckkey, Antero de Quintal, Legobot, Luiz Vasconcelos Filho, Zicane, Mariama Seram,
Astrogildaadroalda e Annimo: 44
Autmato Fonte: http://pt.wikipedia.org/wiki/Aut%C3%B4mato%20%CF%89?oldid=34731615 Contribuidores: Cambraia, Zdtrlik,
KLBot2 e Mapmf
Autmato hbrido Fonte: http://pt.wikipedia.org/wiki/Aut%C3%B4mato%20h%C3%ADbrido?oldid=34731602 Contribuidores: Yanguas, Magioladitis, Reporter, So Silvestre, KLBot2 e Rui Fonte
8.6.2
Imagens
Ficheiro:Buchi_non_deterministic_example.svg
Fonte:
http://upload.wikimedia.org/wikipedia/commons/0/02/Buchi_non_
deterministic_example.svg Licena: CC BY 3.0 Contribuidores: Obra do prprio Artista original: Ashutosh y0078
Ficheiro:Commons-logo.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/4/4a/Commons-logo.svg Licena: Public domain
Contribuidores: This version created by Pumbaa, using a proper partial circle and SVG geometry features. (Former versions used to be
slightly warped.) Artista original: SVG version was created by User:Grunt and cleaned up by 3247, based on the earlier PNG version,
created by Reidab.
Ficheiro:Computer.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/d/d7/Computer.svg Licena: Public domain Contribuidores: The Tango! Desktop Project Artista original: The people from the Tango! project
Ficheiro:DFA_example_multiplies_of_3.svg
Fonte:
http://upload.wikimedia.org/wikipedia/commons/9/94/DFA_example_
multiplies_of_3.svg Licena: Public domain Contribuidores: Obra do prprio Artista original: Self-made
Ficheiro:DFAexample.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/9/9d/DFAexample.svg Licena: Public domain
Contribuidores: Obra do prprio Artista original: Cepheus
Ficheiro:NFAexample.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/0/0e/NFAexample.svg Licena: Public domain Contribuidores: Combination of en:Image:NFAexample.png and Image:DFAexample.svg Artista original: Interiot
Ficheiro:NoFonti.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/b/b5/NoFonti.svg Licena: CC BY-SA 2.5 Contribuidores: Image:Emblem-important.svg Artista original: RaminusFalcon
Ficheiro:Pda-example.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/3/3c/Pda-example.svg Licena: CC BY-SA 3.0
Contribuidores: Obra do prprio Artista original: Jochgem
Ficheiro:Pda-steps.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/2/2e/Pda-steps.svg Licena: CC BY-SA 3.0 Contribuidores: Obra do prprio Artista original: Jochgem
Ficheiro:Pushdown-step.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/c/c0/Pushdown-step.svg Licena: CC BY-SA 3.0
Contribuidores: Obra do prprio Artista original: Jochgem
Ficheiro:Turing_Machine.png Fonte: http://upload.wikimedia.org/wikipedia/commons/b/b7/Turing_Machine.png Licena: Public domain Contribuidores: ? Artista original: ?
Ficheiro:Wikitext.svg Fonte: http://upload.wikimedia.org/wikipedia/commons/c/ce/Wikitext.svg Licena: Public domain Contribuidores: Obra do prprio Artista original: Anomie
8.6.3
Licena