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
Unia\u2dco.
(3) Intersec¸a\u2dco.
(4) Concatenac¸a\u2dco.
(5) Fecho de Kleene.
Prova
Os fechamentos sob complementac¸a\u2dco, unia\u2dco e intersec¸a\u2dco sa\u2dco corola´rios do Teorema 4.
Prova de 4 . Sejam duas linguagens regulares quaisquer L1 e L2. Sejam dois AFD\u2019s
M1 = (E1,\u3a31, \u3b41, i1, F1) e M2 = (E2,\u3a32, \u3b42, i2, F2), tais que L(M1) = L1 e L(M2) = L2,
e tais que E1 \u2229 E2 = \u2205 (e´ fa´cil ver que existem). O seguinte AFN\u3bb M3, definido abaixo,
reconhece L(M1)L(M2) (veja Figura 2.24 para uma representac¸a\u2dco esquema´tica de M3):
M3 = (E1 \u222a E2,\u3a31 \u222a \u3a32, \u3b43, {i1}, F2)
onde \u3b43 e´ dada por:
\u2022 \u3b43(e, a) = {\u3b41(e, a)} para todo e \u2208 E1 e a \u2208 \u3a31;
\u2022 \u3b43(e, a) = {\u3b42(e, a)} para todo e \u2208 E2 e a \u2208 \u3a32;
\u2022 \u3b43(e, \u3bb) = {i2} para todo e \u2208 F1, e \u3b43(e, \u3bb) = \u2205 para e \u2208 (E1 \u222a E2)\u2212 F1.
100
-
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
i\u2032
M
-\u3bb
\ufffd\ufffd\ufffd\ufffdi · · ·
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
...\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
\u3bb
6 \u3bb6
Figura 2.25: Fechamento sob fecho de Kleene.
Prova de 5 . Seja uma linguagem regular qualquer L. Seja um AFD M = (E,\u3a3, \u3b4, i, F )
tal que L(M) = L. O seguinte AFN\u3bb, M \u2032, reconhece L(M)\u2217 (veja Figura 2.25 para uma
representac¸a\u2dco esquema´tica de M \u2032):
M \u2032 = (E \u222a {i\u2032},\u3a3, \u3b4\u2032, {i\u2032}, F \u222a {i\u2032})
onde i\u2032 6\u2208 E, e \u3b4\u2032 e´ dada por:
\u2022 \u3b4\u2032(i\u2032, \u3bb) = {i};
\u2022 \u3b4\u2032(e, a) = {\u3b4(e, a)} para todo e \u2208 E e a \u2208 \u3a3;
\u2022 \u3b4\u2032(e, \u3bb) = {i\u2032} para todo e \u2208 F , e \u3b4\u2032(e, \u3bb) = \u2205 para e \u2208 E \u2212 F .
Observe como a introduc¸a\u2dco de transic¸o\u2dces sob \u3bb torna simples a obtenc¸a\u2dco de AF\u2019s para
os casos da concatenac¸a\u2dco e do fecho de Kleene.
Tre\u2c6s exemplos de aplicac¸o\u2dces das propriedades das linguagens regulares: (1) permitem
provar que uma linguagem e´ regular; (2) permitem provar que uma linguagem na\u2dco e´
regular; e (3) facilitam a obtenc¸a\u2dco de AF para uma linguagem regular.
Seguem-se exemplos das 3 aplicac¸o\u2dces. Primeiramente, uma aplicac¸a\u2dco do tipo (1).
Exemplo 74 Seja a linguagem constitu´\u131da de todas as palavras bina´rias que representem
nu´meros divis´\u131veis por 6, com excec¸a\u2dco daquelas em que o terceiro d´\u131gito da direita para
a esquerda seja 1. Ora, esta linguagem nada mais e´ do que L = L1 \u2212 L2, onde:
\u2022 L1 = {w \u2208 {0, 1}\u2217 | w representa nu´mero divis´\u131vel por 6}; e
\u2022 L2 = {w \u2208 {0, 1}\u2217 | o terceiro d´\u131gito de w, da direita para a esquerda, e´ 1}.
Sabe-se que L1 e L2 sa\u2dco linguagens regulares: as Figuras 2.2, pa´gina 60, e 2.12, pa´gina
75, apresentam AF\u2019s para L1, e a Figura 2.17, pa´gina 87, apresenta AF\u2019s para L2. Como
L = L1\u2212L2 = L1\u2229L2, e a classe das linguagens regulares e´ fechada sob complementac¸a\u2dco
e sob intersec¸a\u2dco (pelo Teorema 9), segue-se que L e´ linguagem regular.
Segue-se um exemplo de aplicac¸a\u2dco do tipo (3).
101
Exemplo 75 Seja a linguagem L do exemplo anterior. Como ressaltado neste exemplo,
L = L1 \u2212 L2, onde:
\u2022 L1 = {w \u2208 {0, 1}\u2217 | w representa nu´mero divis´\u131vel por 6}; e
\u2022 L2 = {w \u2208 {0, 1}\u2217 | o terceiro d´\u131gito de w, da direita para a esquerda, e´ 1}.
Na Figura 2.12, pa´gina 75, tem-se um AFD para L1 e na Figura 2.17, pa´gina 87, tem-se
um AFD para L2. Usando-se as te´cnicas do Teorema 4, pode-se construir facilmente um
AFD para L2 e, em seguida, um AFD para L1 \u2229 L2. Este u´ltimo seria um AFD para L.
Para uma aplicac¸a\u2dco do tipo (2), provar que uma linguagem L na\u2dco e´ regular, raciocina-
se por contradic¸a\u2dco. Primeiramente, supo\u2dce-se que L e´ uma linguagem regular. Depois,
aplica-se uma propriedade de fechamento envolvendo L e, eventualmente, outras lin-
guagens, estas comprovadamente linguagens regulares. Obtendo-se uma linguagem que,
comprovadamente, na\u2dco e´ regular, ter-se-a´ uma contradic¸a\u2dco ja´ que, pela propriedade de
fechamento, deveria ter sido obtida uma linguagem regular. Logo, a suposic¸a\u2dco de que L
seria linguagem regular na\u2dco se sustentaria. Segue-se um exemplo.
Exemplo 76 Seja L = {akbmcn | k = m+ n}. Prova-se, a seguir, que L na\u2dco e´ regular.
Suponha que L e´ uma linguagem regular. Como {a}\u2217{b}\u2217 e´ linguagem regular e a
classe das linguagens regulares e´ fechada sob intersec¸a\u2dco, segue-se que L \u2229 {a}\u2217{b}\u2217 deve
ser uma linguagem regular. Mas, L \u2229 {a}\u2217{b}\u2217 = {anbn | n \u2265 0}, que na\u2dco e´ linguagem
regular. Logo, L na\u2dco e´ linguagem regular.
Exerc´\u131cios
1. Em ambos os Exemplos 63 e 71, nas pa´ginas 79 e 98, mostrou-se que a linguagem
{anbn} | n \u2265 0} na\u2dco e´ regular. Em que diferem ambas as provas?
2. Formalmente, o LB seria enunciado assim: L e´ regular \u2192 \u2203k \u2208 N\u2200z \u2208 L[|z| \u2265
k \u2192 \u2203u, v, w(z = uvw \u2227 |uv| \u2264 k \u2227 |v| \u2265 1 \u2227 \u2200i \u2208 Nuviw \u2208 L)]. Mostre que a
contrapositiva e´: \u2200k \u2208 N\u2203z \u2208 L[|z| \u2265 k\u2227\u2200u, v, w((z = uvw\u2227 |uv| \u2264 k\u2227 |v| \u2265 1)\u2192
\u2203i \u2208 Nuviw 6\u2208 L)]\u2192 L na\u2dco e´ regular.
3. Prove que os seguintes conjuntos na\u2dco sa\u2dco linguagens regulares, utilizando o LB:
(a) {0m1n | m < n}.
(b) {0n12n | n \u2265 0}.
(c) {0m1n0m | m,n \u2265 0}.
(d) {xcx | x \u2208 {a, b}\u2217}.
(e) {10n1n | n \u2265 0}.
(f) {0n2 | n \u2265 0}.
102
4. Prove que os seguintes conjuntos na\u2dco sa\u2dco linguagens regulares, utilizando proprie-
dades de fechamento:
(a) {0, 1}\u2217 \u2212 {0n1n | n \u2265 0}.
(b) {0m1n | m < n} \u222a {0m1n | m > n}.
(c) {w \u2208 {0, 1}\u2217 | o nu´mero de 0\u2019s em w e´ igual ao nu´mero de 1\u2019s}.
(d) {w \u2208 {0, 1}\u2217 | o nu´mero de 0\u2019s em w e´ igual ao nu´mero de 1\u2019s}. \u2212{0n1n | n \u2265
0}.
5. Seja L uma linguagem regular sobre o alfabeto {a, b, c}. Mostre que cada uma das
linguagens seguintes e´ regular:
(a) {w \u2208 L | w conte´m pelo menos um a}.
(b) {w | w \u2208 L ou w conte´m pelo menos um a (ou ambos)}.
(c) {w | ou w \u2208 L ou w conte´m pelo menos um a}.
(d) {w 6\u2208 L | w na\u2dco conte´m a\u2019s}.
6. Complete o Exemplo 75 (pa´gina 102): utilizando a receita dada la´, obtenha um
AFD que reconhec¸a a linguagem constitu´\u131da de todas as palavras bina´rias que
representem nu´meros divis´\u131veis por 6, com excec¸a\u2dco daquelas em que o terceiro
d´\u131gito da direita para a esquerda seja 1.
7. Prove que os seguintes conjuntos sa\u2dco linguagens regulares:
(a) {0m1n | m < n} \u222a {0m1n | m > n}\u222a {0n1n | n \u2265 0}.
(b) {0, 1}\u2217 \u2212 {01, 10}\u2217.
(c) {0n1n | 0 \u2264 n \u2264 101000}.
8. Seja L uma linguagem regular sobre um alfabeto \u3a31. Prove que o conjunto de todas
as palavras sobre \u3a32 (que pode ser igual ou na\u2dco a \u3a31) que te\u2c6m como sufixo alguma
palavra de L e´ linguagem regular.
2.5 Ma´quinas de Mealy e de Moore
As ma´quinas de Mealy e de Moore sa\u2dco auto\u2c6matos finitos com sa´\u131da. Uma ma´quina de
Mealy associa um s´\u131mbolo de sa´\u131da a cada transic¸a\u2dco. E uma ma´quina de Moore associa
um s´\u131mbolo de sa´\u131da a cada estado. Apesar de um ou outro tipo de ma´quina ser mais
conveniente em aplicac¸o\u2dces espec´\u131ficas, uma ma´quina de Moore pode ser convertida em
uma ma´quina de Mealy equivalente, e vice-versa. Neste cap´\u131tulo, sera\u2dco apresentados
ambos os tipos de ma´quina de forma sucinta, assim como os procedimentos de conversa\u2dco
de um tipo em outro.
Uma ma´quina de Moore nada mais e´ do que um AFD com um s´\u131mbolo de sa´\u131da
associado a cada estado, como mostra a definic¸a\u2dco a seguir.
Definic¸a\u2dco 17 Uma ma´quina de Moore e´ uma se\u2c6xtupla (E,\u3a3,\u2206, \u3b4, \u3c3, i), onde:
103
\u2022 E (o conjunto de estados), \u3a3 (o alfabeto de entrada), \u3b4 (a func¸a\u2dco de transic¸a\u2dco) e i
(o estado inicial) sa\u2dco como em AFD\u2019s;
\u2022 \u2206 e´ o alfabeto de sa´\u131da; e
\u2022 \u3c3 : E \u2192 \u2206 e´ a func¸a\u2dco de sa´\u131da, uma func¸a\u2dco total.
Uma ma´quina de Moore funciona de forma similar a um AFD. A diferenc¸a e´ que, ao
inve´s de uma sa´\u131da bina´ria do tipo sim ou na\u2dco, existira´ uma palavra de sa´\u131da; esta e´ inici-
alizada com \u3c3(i) e, ao ser efetuada uma transic¸a\u2dco para um estado e, \u3c3(e) e´ concatenado
a` direita da palavra de sa´\u131da.
Para uma definic¸a\u2dco mais precisa da sa´\u131da computada para uma ma´quina de MooreM ,
sera´ definida a func¸a\u2dco r : E×\u3a3\u2217 \u2192 \u2206\u2217. Dado um estado e e uma palavra w, r(e, w) sera´ a
palavra de sa´\u131da correspondente a` computac¸a\u2dco que leva ao estado \u3b4\u2c6(e, w). A definic¸a\u2dco de
\u3b4\u2c6 para ma´quina de Moore e´ igual a`quela apresentada na Definic¸a\u2dco 2 (pa´gina 65). Segue
a definic¸a\u2dco de r.
Definic¸a\u2dco 18 Seja uma ma´quina de Moore M = (E,\u3a3,\u2206, \u3b4, \u3c3, i). A func¸a\u2dco de sa´\u131da
estendida para M , r : E × \u3a3\u2217 \u2192 \u2206\u2217 e´ definida recursivamente como segue:
(a) r(e, \u3bb) = \u3c3(e);
(b) r(e, ay) = \u3c3(e)r(\u3b4(e, a), y), para todo a \u2208 \u3a3 e y \u2208 \u3a3\u2217.
Com isto, pode-se enta\u2dco definir sa´\u131da de uma ma´quina de Moore.
Definic¸a\u2dco 19 A sa´\u131da computada por uma ma´quina