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

Fundamentos em Teoria da ComputaЗ╞o


DisciplinaFundamentos de Teoria da Computação140 materiais530 seguidores
Pré-visualização50 páginas
de Expresso\u2dces Regulares
(inclusive b\u2019s \u2013 veja o \u201cna\u2dco determinismo\u201d) e seguido por zero ou mais s´\u131mbolos; isto
traduzido em termos de ER e´: (a+ b)\u2217b(a+ b)\u2217.
A segunda abordagem e´ tentar visualizar como as palavras podem ser constru´\u131das,
deterministicamente, da esquerda para a direita ou da direita para a esquerda. Analisan-
do-se uma palavra de L, da esquerda para a direita, determina-se que a mesma pertence a
L quando se encontra um b; isto traduzido em termos de ER e´: a\u2217b(a+b)\u2217. Analisando-se
uma palavra de L, da direita para a esquerda, determina-se que a mesma pertence a L
quando se encontra um b; isto traduzido em termos de ER e´: (a+ b)\u2217ba\u2217.
O mesmo conjunto pode ser denotado por va´rias ER\u2019s, como visto no Exemplo 82.
E´ comum a notac¸a\u2dco r = s, para duas ER\u2019s r e s, para dizer que r e s denotam a
mesma linguagem, ou seja, L(r) = L(s). A`s vezes pode ser interessante tentar obter uma
ER \u201cmais simples\u201d, no sentido de que se possa visualizar com mais facilidade, a partir
dela, qual e´ a linguagem denotada. As propriedades da unia\u2dco, concatenac¸a\u2dco e fecho
de Kleene fornecem subs´\u131dios para obtenc¸a\u2dco de ER\u2019s equivalentes, eventualmente mais
simples. A Tabela 2.1 mostra algumas equivale\u2c6ncias derivadas direta ou indiretamente
de tais propriedades.
Pode-se mostrar que qualquer equivale\u2c6ncia que na\u2dco envolva fecho de Kleene pode
ser derivada a partir das equivale\u2c6ncias 1 a 7 mais as propriedades de associatividade
da unia\u2dco e da concatenac¸a\u2dco, r + (s + t) = (r + s) + t e r(st) = (rs)t, que se esta´
assumindo implicitamente. No entanto, quando se introduz o fecho de Kleene, deixa de
haver um conjunto finito de equivale\u2c6ncias a partir das quais se possa derivar qualquer
equivale\u2c6ncia. Assim, as equivale\u2c6ncias da Tabela 2.1 na\u2dco sa\u2dco suficientes para derivar
qualquer equivale\u2c6ncia. Por outro lado, va´rias sa\u2dco redundantes, no sentido de que podem
ser obtidas a partir de outras. Por exemplo, 13 pode ser obtida a partir de 2, 5 e 10:
\u2205\u2217= (r\u2205)\u2217, por 5
= \u3bb+ r(\u2205r)\u2217\u2205, por 10
= \u3bb+ \u2205, por 5
= \u3bb, por 2.
Exemplo 83 Abaixo segue uma se´rie de simplificac¸o\u2dces de uma ER utilizando as equi-
vale\u2c6ncias da Tabela 2.1. As sub-expresso\u2dces simplificadas em cada passo esta\u2dco sublinhadas.
112
(00\u2217 + 10\u2217)0\u2217(1\u2217 + 0)\u2217= (0 + 1)0\u22170\u2217(1\u2217 + 0)\u2217 por 6
= (0 + 1)0\u2217(1\u2217 + 0)\u2217 por 15
= (0 + 1)0\u2217(1 + 0)\u2217 por 17
= (0 + 1)0\u2217(0 + 1)\u2217 por 1
= (0 + 1)(0 + 1)\u2217 por 19.
Existem va´rias outras equivale\u2c6ncias que podem ser u´teis para simplificac¸a\u2dco de ER\u2019s,
ale´m daquelas exemplificadas na Tabela 2.1. Lembrando que uma ER e´ apenas uma
expressa\u2dco que denota um conjunto sobre um certo alfabeto e que a justaposic¸a\u2dco significa
concatenac¸a\u2dco, \u201c+\u201d significa unia\u2dco e \u201c\u2217\u201d significa fecho de Kleene, e usando-se as propri-
edades conhecidas de tais entidades, pode-se obter novas equivale\u2c6ncias, como mostra o
pro´ximo exemplo.
Exemplo 84 Dados os significados dos operadores, pode-se verificar que (r+ rr+ rrr+
rrrr)\u2217 = r\u2217. Como outro exemplo, considere a ER: ((0(0+1)1+11)0\u2217(00+11))\u2217(0+1)\u2217.
Observando que ela e´ da forma r(0 + 1)\u2217, onde r denota um conjunto de palavras sobre
{0, 1} que conte´m \u3bb, pode-se imediatamente concluir que ela e´ equivalente a (0+1)\u2217, sem
analisar r! Utilizando-se raciocioc´\u131nio ana´logo, pode-se concluir que r\u2217(r + s\u2217) = r\u2217s\u2217:
veja que r\u2217(r + s\u2217) = rr\u2217 + r\u2217s\u2217 e L(rr\u2217) \u2286 L(r\u2217s\u2217).
Uma notac¸a\u2dco bastante u´til e´ r+, onde r e´ uma ER, para significar (rr\u2217). Assim, por
exemplo, a u´ltima ER do Exemplo 83 poderia ser escrita assim: (0 + 1)+. Uma outra
notac¸a\u2dco u´til e´ rn, n \u2265 0; recursivamente:
(a) r0 = \u3bb;
(b) rn = rrn\u22121, para n \u2265 1.
Exemplo 85 O conjunto de todas as palavras de tamanho 10 sob {0, 1} e´ denotado
por (0 + 1)10. Como outro exemplo, considere as equivale\u2c6ncias da seguinte forma: r\u2217 =
(rn)\u2217(\u3bb + r + r2 + · · · + rn\u22121), para n > 1 (observe que para n = 2, tem-se a identidade
12 da Tabela 2.1).
A seguir, mostra-se que toda linguagem regular e´ denotada por uma expressa\u2dco regular
e vice-versa, que toda expressa\u2dco regular denota uma linguagem regular.
Teorema 12 Toda expressa\u2dco regular denota uma linguagem regular.
Prova
A prova sera´ feita por induc¸a\u2dco construtiva, ou seja, sera´ mostrado (a) como construir
AF\u2019s para os elementos primitivos dos conjuntos regulares, quais sejam, \u2205, {\u3bb} e {a} para
cada a \u2208 \u3a3, e (b) como combinar AF\u2019s para simular as operac¸o\u2dces de unia\u2dco, concatenac¸a\u2dco
e fecho de Kleene. A Figura 2.30 mostra diagramas de estado para AF\u2019s que reconhecem
\u2205, {\u3bb} e {a}. Resta enta\u2dco mostrar que, dados AF\u2019s para duas linguagens L1 e L2, e´
poss´\u131vel construir AF\u2019s para L1 \u222aL2, L1L2 e L\u22171. Mas isto ja´ foi mostrado no Teorema 9.
113
-
\ufffd\ufffd\ufffd\ufffd \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
(a) AF para \u2205
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
(a) AF para {\u3bb}
-
\ufffd\ufffd\ufffd\ufffd-a \ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
(a) AF para {a}
Figura 2.30: AF\u2019s para \u2205, {\u3bb} e {a}.
(Observe que os AF\u2019s da Figura 2.30 sa\u2dco AFD\u2019s. A prova do Teorema 9 constro´i AFD
para L1 \u222a L2, a partir de quaisquer AFD\u2019s para L1 e L2, e AFN\u3bb\u2019s para L1L2 e L\u22171 a
partir de quaisquer AFD\u2019s para L1 e L2. E os Teoremas 8 e 7, em sequ¨e\u2c6ncia, mostram
como construir AFD\u2019s a partir de AFN\u3bb\u2019s. Assim, conclui-se, na\u2dco apenas que e´ poss´\u131vel
construir AFD\u2019s para quaisquer conjuntos regulares, como tambe´m tem-se uma forma de
constru´\u131-los.)
A construc¸a\u2dco de um AFD que reconhece a linguagem denotada por uma ER usando os
passos apontados no final da prova do Teorema 12, que envolve a aplicac¸a\u2dco das te´cnicas
dos Teoremas 9, 8 e 7, e´ bastante trabalhosa, mesmo para ER\u2019s relativamente simples.
Nos Exerc´\u131cios 34 e 35, no final do cap´\u131tulo, sa\u2dco propostos dois outros me´todos, um
para obtenc¸a\u2dco de um AFN\u3bb, e outro para obtenc¸a\u2dco de um AFN. O primeiro gera AF\u2019s
ainda maiores e mais redundantes, mas e´ conceitualmente bastante simples, sendo, in-
clusive, o me´todo usualmente apresentado em textos de linguagens formais. O segundo,
embora ainda possa gerar AFN\u2019s grandes e redundantes, pode servir de base para uma
implementac¸a\u2dco real.
A prova do teorema seguinte mostra como construir uma ER que denota a linguagem
reconhecida por um AFD. Antes, pore´m, deve-se introduzir uma extensa\u2dco do conceito de
diagrama de estados de um AF, que sera´ denominado diagrama ER.
Definic¸a\u2dco 25 Um diagrama ER sobre \u3a3 e´ um diagrama de estados cujas arestas, ao
inve´s de serem rotuladas com s´\u131mbolos do alfabeto \u3a3, sa\u2dco rotuladas com ER\u2019s sobre \u3a3.
Uma transic¸a\u2dco sob uma ER r pode ser imaginada como representando uma sub-
ma´quina que le\u2c6 qualquer palavra do conjunto denotado por r. Seja, por exemplo, a
transic¸a\u2dco:
\ufffd\ufffd\ufffd\ufffde -(0 + 1)1(0 + 1)
\u22170 \ufffd\ufffd\ufffd\ufffde\u2032
Do estado e ha´ transic¸a\u2dco para e\u2032 sob w se, e somente se, w \u2208 L((0 + 1)1(0 + 1)\u22170), ou
seja, o segundo s´\u131mbolo de w e´ 1 e o u´ltimo e´ 0. Assim, por exemplo, as menores palavras
para as quais ha´ transic¸a\u2dco de e para e\u2032 sa\u2dco 010 e 110.
Os exerc´\u131cios 36 e 37 no final do cap´\u131tulo permitem formular o conceito de linguagem
definida por um diagrama ER. A prova do pro´ximo teorema mostra como obter uma ER
a partir de um diagrama ER.
114
\ufffd\ufffd\ufffd\ufffde1 -r1\ufffd\ufffd\ufffd\ufffde
\ufffd\ufffd
?
r2
-r3
\ufffd\ufffd\ufffd\ufffde2
@@ \ufffd\ufffd\ufffd\ufffd\ufffd\ufffde1 -r1r
\u2217
2r3 \ufffd\ufffd\ufffd\ufffde2
(a) e1 6= e2
\ufffd\ufffd \ufffd\ufffde1 = e2 -r1
\ufffd\ufffd\ufffd\ufffde \ufffd\ufffd\ufb00 r2\ufb00
r3
@@ \ufffd\ufffd\ufffd\ufffd \ufffd\ufffde1 = e2 \ufffd\ufffd\ufb00 r1r\u22172r3
(b) e1 = e2
Figura 2.31: Eliminado um estado de um diagrama ER
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
i
\ufffd\ufffd
?
r
(a) Diagrama ER para r\u2217
-
\ufffd\ufffd\ufffd\ufffdi
\ufffd\ufffd
?
q
-
r
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
fk
\ufffd\ufffd
?
s
\ufb00 t
(b) Diagrama ER para q\u2217r(s+ tq\u2217r)\u2217
Figura 2.32: Diagramas ER ba´sicos
Teorema 13 Toda linguagem regular e´ denotada por alguma expressa\u2dco regular.
Prova
Seja um AFD M = (E,\u3a3, \u3b4, i, {f1, f2, . . . , fn}). Primeiramente, note que L(M) =
L1(M) \u222a L2(M) \u222a · · · \u222a Ln(M), onde Lk(M) = {w \u2208 \u3a3\u2217 | \u3b4\u2c6(i, w) = fk} para 1 \u2264 k \u2264 n.
Seja pk uma expressa\u2dco regular para Lk(M). Enta\u2dco L(M) seria denotada por meio da
expressa\u2dco regular: p1 + p2 + · · · + pn. Assim, o problema se reduz a encontrar uma ER
pk, para cada Lk(M). Abaixo, mostra-se como fazer isto a partir de um diagrama ER
obtido a partir de M .
Inicialmente, o diagrama ER e´ como o diagrama de estados deM , apenas consideran-
do-se cada transic¸a\u2dco sob um s´\u131mbolo a como uma transic¸a\u2dco sob uma ER a.