Fundamentos em Teoria da ComputaЗ╞o
303 pág.

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação141 materiais535 seguidores
Pré-visualização50 páginas
segundo exemplo, o
nome de um estado indica o resto da divisa\u2dco por 6 do nu´mero representado pelo prefixo
que leva ate´ o estado. No terceiro exemplo, o nome de um estado indica o andar em que
o elevador esta´ e se ele esta´ subindo ou descendo. E´ evidente que a concepc¸a\u2dco de cada
um dos auto\u2c6matos, e o entendimento de cada um deles, sa\u2dco muito facilitados usando-se
tais nomes ao inve´s de se usar nomes arbitra´rios.
O fato de que um auto\u2c6mato tem apenas um estado inicial na\u2dco diminui seu poder
computacional. Sera´ mostrado mais adiante que o poder computacional de um auto\u2c6mato
finito na\u2dco determin´\u131stico, que e´ o caso de um auto\u2c6mato com mais de um estado inicial, e´
o mesmo de um AFD.
A Definic¸a\u2dco 1 modela as transic¸o\u2dces de um AFD como uma func¸a\u2dco que mapeia cada
par (estado, s´\u131mbolo) para um estado. Este fato, que cada par (estado, s´\u131mbolo) leva a
63
um u´nico estado, e´ que caracteriza o determinismo do AFD: a partir do estado inicial, so´
e´ poss´\u131vel atingir um u´nico estado para uma dada palavra de entrada. E o fato de que a
func¸a\u2dco e´ total garante que para toda palavra de entrada atinge-se um estado consumindo-
se toda a palavra. Esta exige\u2c6ncia simplifica o modelo, facilitando sua manipulac¸a\u2dco do
ponto de vista teo´rico, sem impor qualquer limitac¸a\u2dco quanto ao seu poder computacional.
Para conciliar o primeiro exemplo da Sec¸a\u2dco 2.1 com a definic¸a\u2dco de AFD, basta inserir
mais um estado, digamos t (de \u201ctrage´dia\u201d), e fazer \u3b4(e, a) = t se na\u2dco existir transic¸a\u2dco de
e para algum estado sob a; em particular, \u3b4(t, a) = t para todo a \u2208 {s, l, c, r}. Com isto,
o exemplo pode ser modelado mediante o auto\u2c6mato (veja Figura 2.1, pa´gina 58)
(E, {s, l, c, r}, \u3b4, {h, l, c, r}, {{}})
onde E e´ o conjunto
{{h, l, c, r}, {l, r}, {h, l, r}, {l}, {r}, {h, l, c}, {h, c, r}, {c}, {h, c}, {}, t}
e \u3b4 e´ dada por3:
\u3b4 s l c r
{h, l, c, r} t t {l, r} t
{l, r} {h, l, r} t {h, l, c, r} t
{h, l, r} {l, r} {r} t {l}
{l} t t {h, l, c} {h, l, r}
{r} t {h, l, r} {h, c, r} t
{h, l, c} t {c} {l} t
{h, c, r} t t {r} {c}
{c} {h, c} {h, l, c} t {h, c, r}
{h, c} {c} t {} t
{} t t {h, c} t
t t t t t
Assim, para ficar conforme a definic¸a\u2dco de AFD, o diagrama de estados da Figura 2.1
deveria ser alterado para conter o estado t e as transic¸o\u2dces relativas a t acima especificadas.
No entanto, e´ u´til assumir que, caso alguma transic¸a\u2dco de algum estado e sob algum
s´\u131mbolo a na\u2dco esteja especificada no diagrama de estados, enta\u2dco existe um estado (na\u2dco
mostrado no diagrama) e\u2032 tal que:
\u2022 existe uma transic¸a\u2dco de e para e\u2032 sob a;
\u2022 e\u2032 na\u2dco e´ estado final;
\u2022 existe uma transic¸a\u2dco de e\u2032 para e\u2032 sob cada s´\u131mbolo do alfabeto.
Observe que os dois u´ltimos itens implicam que se e\u2032 e´ atingido apo´s consumida parte de
uma palavra, enta\u2dco o sufixo que se seguir e´ irrelevante: ele na\u2dco ira´ alterar o fato de que a
palavra na\u2dco e´ reconhecida. Em muitas aplicac¸o\u2dces este estado e´ referido como um estado
de erro, o que e´ consistente com o primeiro exemplo da sec¸a\u2dco anterior, na forma em que
3Neste formato tabular, uma func¸a\u2dco f e´ representada de forma que f(i, j) e´ exibido na linha i, coluna
j.
64
ele foi modelado. Embora nem todas as aplicac¸o\u2dces contenham este \u201cestado de erro\u201d,
naquelas em que ele esta´ presente, muitas vezes a sua omissa\u2dco no diagrama de estados
simplifica o diagrama, tornando-o mais leg´\u131vel. E´ este o caso do primeiro exemplo da
sec¸a\u2dco anterior.
Deste ponto em diante, quando se quiser enfatizar que foram omitidos todos os es-
tados de erro porventura existentes, dir-se-a´ que o diagrama e´ um diagrama de estados
simplificado.
O segundo exemplo da sec¸a\u2dco anterior, que na\u2dco tem \u201cestado de erro\u201d, pode ser mode-
lado mediante o auto\u2c6mato
({0, 1, 2, 3, 4, 5}, {0, 1}, \u3b4, 0, {0})
onde \u3b4 e´ dada por:
\u3b4 0 1
0 0 1
1 2 3
2 4 5
3 0 1
4 2 3
5 4 5
Como ficou dito acima, para qualquer palavra existe um, e apenas um, estado do
auto\u2c6mato que pode ser alcanc¸ado a partir do estado inicial (e de qualquer outro estado).
Assim, define-se abaixo uma func¸a\u2dco que, dado um estado e e uma palavra w, da´ o estado
alcanc¸ado. Evidentemente, ela deve coincidir com a func¸a\u2dco de transic¸a\u2dco para palavras de
tamanho 1.
Definic¸a\u2dco 2 Seja um AFD M = (E,\u3a3, \u3b4, i, F ). A func¸a\u2dco de transic¸a\u2dco estendida para
M , \u3b4\u2c6, e´ uma func¸a\u2dco de E × \u3a3\u2217 para E, definida recursivamente como segue:
(a) \u3b4\u2c6(e, \u3bb) = e;
(b) \u3b4\u2c6(e, ay) = \u3b4\u2c6(\u3b4(e, a), y), para todo a \u2208 \u3a3 e y \u2208 \u3a3\u2217.
Observe como \u3b4\u2c6(e, a) coincide com \u3b4(e, a):
\u3b4\u2c6(e, a) = \u3b4\u2c6(\u3b4(e, a), \u3bb) por b, Definic¸a\u2dco 2
= \u3b4(e, a) por a, Definic¸a\u2dco 2.
Exemplo 54 Seja o AFD do segundo exemplo da sec¸a\u2dco anterior, cujo diagrama de esta-
dos e´ mostrado na Figura 2.2, pa´gina 60. Observe como o estado atingido processando-se
a palavra 1010 a partir do estado inicial, 0, e´ 4:
\u3b4\u2c6(0, 1010) = \u3b4\u2c6(\u3b4(0, 1), 010) por b, Definic¸a\u2dco 2
= \u3b4\u2c6(1, 010) pois \u3b4(0, 1) = 1
= \u3b4\u2c6(\u3b4(1, 0), 10) por b, Definic¸a\u2dco 2
= \u3b4\u2c6(2, 10) pois \u3b4(1, 0) = 2
= \u3b4\u2c6(\u3b4(2, 1), 0) por b, Definic¸a\u2dco 2
= \u3b4\u2c6(5, 0) pois \u3b4(2, 1) = 5
= \u3b4\u2c6(\u3b4(5, 0), \u3bb) por b, Definic¸a\u2dco 2
= \u3b4\u2c6(4, \u3bb) pois \u3b4(5, 0) = 4
= 4 por a, Definic¸a\u2dco 2.
65
Utilizando-se \u3b4\u2c6, pode-se definir a linguagem reconhecida, ou aceita, por um AFD.
Definic¸a\u2dco 3 A linguagem reconhecida (aceita) por um AFD M = (E,\u3a3, \u3b4, i, F ) e´ o
conjunto L(M) = {w \u2208 \u3a3\u2217 | \u3b4\u2c6(i, w) \u2208 F}. Uma determinada palavra w \u2208 \u3a3\u2217 e´ dita ser
reconhecida, ou aceita, por M se, e somente se, \u3b4\u2c6(i, w) \u2208 F .
Assim, a linguagem aceita pelo AFD do primeiro exemplo e´ o conjunto de todas as
palavras que representam sequ¨e\u2c6ncias de movimentos que propiciam o transporte seguro
dos elementos citados. E a linguagem aceita pelo AFD do segundo exemplo e´ o conjunto
de toda palavra bina´ria que represente um nu´mero divis´\u131vel por 6.
No primeiro exemplo, o objetivo era encontrar uma palavra w tal que \u3b4\u2c6(i, w) \u2208 F .
E no segundo, o objetivo era ter uma ma´quina abstrata para determinar, para qualquer
palavra w, se \u3b4\u2c6(i, w) \u2208 F . No primeiro caso, basta usar um algoritmo para determinar
um caminho entre dois ve´rtices em um grafo. E no segundo, a resposta e´ o pro´prio AFD
obtido. Assim, embora o objetivo original em cada exemplo seja diferente, em ambos
foram obtidos reconhecedores de linguagens.
Em princ´\u131pio, pode-se pensar em implementar um dado AFD, visto como reconhe-
cedor, nas mais diversas tecnologias, inclusive via um procedimento. Neste u´ltimo caso,
pode-se usar qualquer paradigma de programac¸a\u2dco, como o procedural, o funcional ou o
lo´gico. Tendo em vista que os maiores usua´rios deste livro sa\u2dco estudantes de informa´tica,
e que, pelo menos por enquanto, o paradigma procedural e´ mais comum, sera´ exem-
plificado como implementar um AFD neste u´ltimo paradigma. O procedimento usa as
seguintes varia´veis para representar o AFD:
\u2022 i: estado inicial;
\u2022 F : conjunto dos estados finais;
\u2022 D, uma matriz de leitura-apenas, contendo a func¸a\u2dco de transic¸a\u2dco, de forma que
D[e, a] = \u3b4(e, a) para todo estado e e s´\u131mbolo a.
Assume-se a existe\u2c6ncia de um procedimento do tipo func¸a\u2dco, prox , que retorna o pro´ximo
s´\u131mbolo de entrada, quando houver, e fs (fim de sequ¨e\u2c6ncia), quando na\u2dco houver. O
algoritmo esta´ mostrado na Figura 2.5. Observe que este procedimento e´ geral, podendo
ser aplicado a qualquer AFD recebido como entrada. Uma abordagem que resulta em
maior eficie\u2c6ncia, mas que leva a` obtenc¸a\u2dco de um procedimento espec´\u131fico para um AFD,
e´ codificar cada transic¸a\u2dco como se fosse uma \u201cinstruc¸a\u2dco\u201d (veja exerc´\u131cio 7 proposto no
final da Sec¸a\u2dco 2.2, na pa´gina 82). De qualquer forma, em ambos os casos, o tempo de
execuc¸a\u2dco e´ diretamente proporcional ao tamanho da palavra de entrada.
Exemplo 55 Uma das aplicac¸o\u2dces de AFD\u2019s e´ a ana´lise le´xica de compiladores de lingua-
gens de programac¸a\u2dco, como Pascal, C e Java. Nesta fase, sa\u2dco reconhecidas determinadas
entidades sinta´ticas, como identificadores, constantes inteiras, constantes reais, palavras-
chave, etc. Na Figura 2.6 esta´ mostrado o diagrama de estados de um AFD para reco-
nhecimento de constantes reais