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
porque na\u2dco ha´ APD para as seguintes linguagens:
(a) {wwR | w \u2208 {1, 2}\u2217}.
147
(b) {0m1n | m > n}.
(c) {0m1n | m 6= n}.
(d) {w \u2208 {0, 1}\u2217 | o nu´mero de 0\u2019s em w e´ maior que o de 1\u2019s}.
5. Construa um APD que reconhec¸a toda palavra com pare\u2c6nteses balanceados. Exem-
plos de palavras da linguagem: \u3bb, (), (())(). Exemplos de palavras que na\u2dco
pertencem a` linguagem: (, )(, ()).
Generalize para o caso em que existem n tipos de pare\u2c6nteses. Neste caso, considere
que cada ocorre\u2c6ncia de um abre pare\u2c6nteses, ai, tem de ser seguida a` direita por
uma ocorre\u2c6ncia do fecha pare\u2c6nteses respectivo, bi, sendo que entre ai e bi so´ pode
ocorrer uma palavra com pare\u2c6nteses balanceados. Se i = 2, a1 = (, b1 = ), a2 = [,
b2 = ], seriam exemplos de palavras da linguagem: \u3bb, (), [()](), [[()]()]([]).
Exemplos de palavras que na\u2dco pertencem a` linguagem: (, ][, ()], (], ([)].
6. Construa um APD que reconhec¸a as expresso\u2dces aritme´ticas na forma prefixada,
EAPre, definidas recursivamente como segue:
(a) t e´ uma EAPre;
(b) se x e y sa\u2dco EAPre\u2019s, enta\u2dco +xy e \u2212xy sa\u2dco EAPre\u2019s.
Sugesta\u2dco: sempre que ler + ou -, empilhe dois X\u2019s, para \u201clembrar\u201d de ler duas
subexpresso\u2dces a` frente.
7. Construa um APD que reconhec¸a as expresso\u2dces aritme´ticas na forma posfixada,
EAPos, definidas recursivamente como segue:
(a) t e´ uma EAPos;
(b) se x e y sa\u2dco EAPos\u2019s, enta\u2dco xy+ e xy\u2212 sa\u2dco EAPos\u2019s.
Sugesta\u2dco: use os seguintes fatos, fa´ceis de mostrar por induc¸a\u2dco: o nu´mero de t\u2019s e´
um a mais que o de operadores, e qualquer palavra que tenha mais t\u2019s que opera-
dores e´ prefixo de EAPos.
3.3 Auto\u2c6matos com Pilha Na\u2dco Determin´\u131sticos
A diferenc¸a entre um auto\u2c6mato com pilha determin´\u131stico e um na\u2dco determin´\u131stico e´ que
este u´ltimo pode conter transic¸o\u2dces compat´\u131veis, como visto na definic¸a\u2dco a seguir.
Definic¸a\u2dco 31 Um auto\u2c6mato com pilha na\u2dco determin´\u131stico (APN) e´ uma se\u2c6xtupla (E,\u3a3,\u393, \u3b4, I, F ),
onde
\u2022 E, \u3a3, \u393 e F sa\u2dco como em APD\u2019s;
\u2022 \u3b4, a func¸a\u2dco de transic¸a\u2dco, e´ uma func¸a\u2dco parcial de E × (\u3a3 \u222a {\u3bb})× (\u393 \u222a {\u3bb}) para
D, onde D e´ constitu´\u131do dos subconjuntos finitos de E × \u393\u2217;
\u2022 I, um subconjunto de E, e´ o conjunto de estados iniciais.
148
A relac¸a\u2dco
\u2217` da Definic¸a\u2dco 29, pa´gina 142, sera´ utilizada para definir reconhecimento
para APN\u2019s, de forma similar ao reconhecimento para APD\u2019s apresentado na Definic¸a\u2dco 30.
Definic¸a\u2dco 32 Seja um APN M = (E,\u3a3,\u393, \u3b4, I, F ). A linguagem reconhecida por M e´
L(M) = {w \u2208 \u3a3\u2217 | [i, w, \u3bb] \u2217` [e, \u3bb, \u3bb] e e \u2208 F para algum i \u2208 I}.
Uma palavra w tal que [i, w, \u3bb]
\u2217` [e, \u3bb, \u3bb], onde i \u2208 I e e \u2208 F , e´ dita ser reconhecida
(aceita) por M .
Segue um exemplo que mostra a evoluc¸a\u2dco de um APD para um APN equivalente
\u201cmais conciso\u201d.
Exemplo 97 No Exemplo 94, pa´gina 142, foi visto um APD para a linguagem
{w | w \u2208 {0, 1}\u2217 e o nu´mero de 0\u2019s em w e´ igual ao de 1\u2019s}.
Neste APD e´ usado o s´\u131mbolo F para marcar o fundo da pilha, de forma que, quando os
nu´meros de 0\u2019s e de 1\u2019s se tornam ide\u2c6nticos (mesmo que a palavra na\u2dco tenha sido toda
processada ainda), seja ativada a transic¸a\u2dco para o estado final igual . Ora, um auto\u2c6mato
na\u2dco determin´\u131stico pode \u201cadivinhar\u201d quando a pilha se torna vazia e fazer a transic¸a\u2dco
citada. Assim, um APN equivalente ao APD do Exemplo 94 seria:
N = ({igual , dif }, {0, 1}, {Z, U}, \u3b4, {igual}, {igual}),
onde \u3b4 e´ dada por:
1. \u3b4(igual , 0, \u3bb) = {[dif , Z]}
2. \u3b4(igual , 1, \u3bb) = {[dif , U]}
3. \u3b4(dif , 0, Z) = {[dif , ZZ]}
4. \u3b4(dif , 0, U) = {[dif , \u3bb]}
5. \u3b4(dif , 1, U) = {[dif , UU]}
6. \u3b4(dif , 1, Z) = {[dif , \u3bb]}
7. \u3b4(dif , \u3bb, \u3bb) = {[igual , \u3bb]}.
Veja o diagrama de estados de N na Figura 3.9. Note que a u´nica diferenc¸a com relac¸a\u2dco
ao APD do Exemplo 94 e´ que o s´\u131mbolo F que la´ ocorre foi substitu´\u131do por \u3bb.
Observe que a transic¸a\u2dco 7 e´ compat´\u131vel com as transic¸o\u2dces 3 a 6, mas de uma forma
restrita: partindo-se do estado dif , quando a pilha esta´ vazia, apenas a transic¸a\u2dco 7 e´
aplica´vel; somente quando a pilha na\u2dco esta´ vazia, uma das transic¸o\u2dces 3 a 6 e´ aplica´vel,
ale´m da transic¸a\u2dco 7. Assim, se for dada prioridade sempre para as transic¸o\u2dces 3 a 6, o
comportamento do APN e´ ana´logo ao do APD do Exemplo 94. Isto evidencia que este
149
-
\ufffd\ufffd \ufffd\ufffd\ufffd\ufffd \ufffd
igual -
1, \u3bb/U
0, \u3bb/Z
\ufb00
\u3bb, \u3bb/\u3bb
\ufffd\ufffd \ufffd\ufffddif \ufffd\ufffd\ufb00 0, U/\u3bb
0, Z/ZZ
1, U/UU
1, Z/\u3bb
Figura 3.9: APN para nu´mero igual de 0\u2019s e 1\u2019s.
-
\ufffd\ufffd \ufffd\ufffd\ufffd\ufffd \ufffd
igual -
1, \u3bb/U
0, \u3bb/Z
\ufb00
\u3bb, \u3bb/\u3bb
\ufffd\ufffd \ufffd\ufffddif \ufffd\ufffd\ufb00 0, U/\u3bb1, Z/\u3bb
(a) O segundo.
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
\ufffd\ufffd
?
0, U/\u3bb
0, \u3bb/Z;
\ufffd\ufffd6
1, Z/\u3bb
1, \u3bb/U;
(b) O terceiro.
Figura 3.10: Mais dois APN\u2019s para nu´mero igual de 0\u2019s e 1\u2019s.
APN reconhece toda palavra que o referido APD reconhece. Por outro lado, tal APN
continua na\u2dco podendo reconhecer palavras com nu´meros diferentes de 0\u2019s e 1\u2019s, como
pode ser notado verificando-se o padra\u2dco de empilhamentos e desempilhamentos.
Na realidade, o APN N e´ menos conciso do que poderia ser. Observe que as transic¸o\u2dces
3 e 5 sa\u2dco desnecessa´rias. O mesmo efeito da transic¸a\u2dco 3 pode ser conseguido aplicando-se,
em sequ¨e\u2c6ncia, as transic¸o\u2dces 7 (compat´\u131vel com a 3) e 1, e o mesmo efeito da transic¸a\u2dco 5
pode ser conseguido aplicando-se, em sequ¨e\u2c6ncia, as transic¸o\u2dces 7 (compat´\u131vel com a 5) e 2.
Obte´m-se, com isto, o APN cujo diagrama de estados esta´ mostrado na Figura 3.10(a).
Analisando-se este u´ltimo diagrama de estados, levando-se em conta que o reconhecimento
se da´ quando a pilha fica vazia, chega-se ao APN equivalente cujo diagrama de estados
esta´ na Figura 3.10(b).
A seguir, e´ apresentado um APN para uma linguagem que na\u2dco pode ser reconhecida
por APD\u2019s.
Exemplo 98 Na Figura 3.11 esta´ mostrado o diagrama de estados para um APN que re-
conhece a linguagem dos pal´\u131ndromos sobre o alfabeto {0, 1}, ou seja, {w \u2208 {0, 1}\u2217 | w =
wR}.
Caso uma palavra w seja pal´\u131ndromo, existira´ uma computac¸a\u2dco para w em que w e´
consumida e a pilha fica vazia; para tal computac¸a\u2dco, uma das 3 transic¸o\u2dces de 1 para 2 e´
percorrida:
\u2022 se |w| for par, e´ percorrida a transic¸a\u2dco de 1 para 2 sob \u3bb;
\u2022 se |w| for \u131´mpar e o s´\u131mbolo do meio for 0, e´ percorrida a transic¸a\u2dco de 1 para 2 sob
0;
150
-
\ufffd\ufffd\ufffd\ufffd1 -\u3bb, \u3bb/\u3bb;
0, \u3bb/\u3bb;
1, \u3bb/\u3bb
\ufffd\ufffd\ufffd\ufffd2\ufffd\ufffd\ufffd
\ufffd\ufffd
?
1, \u3bb/1
0, \u3bb/0; \ufffd\ufffd
?
1, 1/\u3bb
0, 0/\u3bb;
Figura 3.11: APN para pal´\u131ndromos sobre {0, 1}\u2217.
\u2022 se |w| for \u131´mpar e o s´\u131mbolo do meio for 1, e´ percorrida a transic¸a\u2dco de 1 para 2 sob
1.
Ao processar uma palavra da esquerda para a direita, quando e´ atingido o meio da
palavra, na\u2dco ha´ como o auto\u2c6mato reconhecer tal fato, para, a partir da´\u131, comparar a
segunta metade com a primeira. Assim sendo, na\u2dco ha´ como construir um APD para a
linguagem dos pal´\u131ndromos.
Pela Definicao 32, a linguagem reconhecida por um APN M = (E,\u3a3,\u393, \u3b4, I, F ) e´
L(M) = {w \u2208 \u3a3\u2217 | [i, w, \u3bb] \u2217` [e, \u3bb, \u3bb] e e \u2208 F para algum i \u2208 I}.
Uma definic¸a\u2dco alternativa, que levaria a uma concepc¸a\u2dco diferente de APN\u2019s, e´ aquela
em que o reconhecimento de uma palavra se da´ ao ser atingido um estado final, apo´s
consumida a palavra de entrada, esteja a pilha vazia ou na\u2dco. Usando o \u131´ndice F em
LF (M) para significar reconhecimento por estado final , segue tal definic¸a\u2dco alternativa,
mais formalmente.
Definic¸a\u2dco 33 Seja um APN M = (E,\u3a3,\u393, \u3b4, I, F ). A linguagem reconhecida por M
por estado final e´
LF (M) = {w \u2208 \u3a3\u2217 | [i, w, \u3bb]
\u2217` [e, \u3bb, y],
onde y \u2208 \u393\u2217, e e \u2208 F para algum i \u2208 I}.
Uma palavra w tal que [i, w, \u3bb]
\u2217` [e, \u3bb, y], onde y \u2208 \u393\u2217, i \u2208 I e e \u2208 F , e´ dita ser
reconhecida (aceita) por M por estado final.
O reconhecimento segundo a Definic¸a\u2dco 32 sera´ denominado a seguir de reconhecimento
por pilha vazia e estado final .
Pode-se mostrar que uma linguagem pode ser reconhecida por pilha vazia e estado final
se, e somente se, pode ser reconhecida por estado final, como sera´ visto no Teorema 16
no final desta sec¸a\u2dco.
O exemplo a seguir mostra dois auto\u2c6matos com pilha que reconhecem a mesma lin-
guagem, um deles usando reconhecimento por pilha vazia e estado final, e o outro usando
reconhecimento por estado final.
Exemplo 99 Seja o problema de determinar um APN que reconhec¸a a linguagem