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
(d) O conjunto das palavras com nu´meros \u131´mpar de 0\u2019s e \u131´mpar de 1\u2019s.
9. Modifique o algoritmo para obtenc¸a\u2dco de uma ER a partir de um AFD, mostrado
na Figura 2.33, pa´gina 116, para a obtenc¸a\u2dco de uma ER a partir de:
(a) Um AFN.
(b) Um AF\u3bb.
10. Que tipo de linguagem pode ser denotada por uma ER sem ocorre\u2c6ncias de fecho de
Kleene?
119
2.7 Grama´ticas Regulares
Uma grama´tica regular prove\u2c6 mais uma forma de especificar uma linguagem regular.
Enquanto auto\u2c6matos finitos permitem a especificac¸a\u2dco de uma linguagem via um reconhe-
cedor para a mesma, e expresso\u2dces regulares permitem a especificac¸a\u2dco via uma expressa\u2dco
que a denota, grama´ticas regulares permitem a especificac¸a\u2dco via um gerador para mesma.
Ou seja, mediante uma grama´tica regular, mostra-se como gerar todas, e apenas, as pa-
lavras de uma linguagem.
Definic¸a\u2dco 26 Uma grama´tica regular (GR) e´ uma grama´tica (V,\u3a3, R, P ), em que cada
regra tem uma das formas:
\u2022 X \u2192 a
\u2022 X \u2192 aY
\u2022 X \u2192 \u3bb
onde X,Y \u2208 V e a \u2208 \u3a3.
Uma caracter´\u131stica interessante das GR\u2019s e´ o formato das formas sentenciais geradas:
wA, onde w so´ tem terminais e A e´ uma varia´vel.
Exemplo 87 Seja L = {w \u2208 {a, b, c}\u2217 | w na\u2dco conte´m abc}. Uma GR que gera L seria
({A,B,C}, {a, b, c}, R,A), onde R conte´m as regras:
A\u2192 aB|bA|cA|\u3bb
B \u2192 aB|bC|cA|\u3bb
C \u2192 aB|bA|\u3bb
A seguir, mostra-se que as grama´ticas regulares geram apenas linguagens regulares
e, vice-versa, que toda linguagem regular e´ gerada por grama´tica regular. No teorema
a seguir, mostra-se como construir um AFN que reconhece a linguagem gerada por uma
grama´tica regular. A cada varia´vel da grama´tica ira´ corresponder um estado do AFN, e
a cada regra ira´ corresponder uma transic¸a\u2dco.
Teorema 14 Toda grama´tica regular gera uma linguagem regular.
Prova
Seja uma GR G = (V,\u3a3, R, P ). Sera´ mostrado como construir um AFN M =
(E,\u3a3, \u3b4, {P}, F ) tal que L(M) = L(G). Deve-se construir M de forma que P \u2217\u21d2
w se, e somente se, \u3b4\u2c6({P}, w) \u2229 F 6= \u2205. Para isto, seja algum Z 6\u2208 V . Enta\u2dco:
\u2022 E =
{
V \u222a {Z} se R conte´m regra da forma X \u2192 a
V caso contra´rio.
\u2022 Para toda regra da forma X \u2192 aY fac¸a Y \u2208 \u3b4(X, a), e para toda regra da forma
X \u2192 a fac¸a Z \u2208 \u3b4(X, a).
120
\u2022 F =
{ {X|X \u2192 \u3bb \u2208 R} \u222a {Z} se Z \u2208 E
{X|X \u2192 \u3bb \u2208 R} caso contra´rio.
Inicialmente, mostra-se por induc¸a\u2dco sobre |w| que:
P
\u2217\u21d2 wX se, e somente se, X \u2208 \u3b4\u2c6({P}, w) para w \u2208 \u3a3\u2217 e X \u2208 V . (2.4)
Pelo formato das regras de G, |w| \u2265 1. Assim, considere w = a \u2208 \u3a3. Tem-se:
P
\u2217\u21d2 aX\u2194 P \u2192 aX \u2208 R pela definic¸a\u2dco de \u2217\u21d2 e Definic¸a\u2dco 26
\u2194 X \u2208 \u3b4(P, a) pela definic¸a\u2dco de \u3b4
\u2194 X \u2208 \u3b4\u2c6({P}, a) pela definic¸a\u2dco de \u3b4\u2c6(Definic¸a\u2dco 10).
Suponha que 2.4 vale para um certo w \u2208 \u3a3+ arbitra´rio. Prova-se que vale para aw para
a \u2208 \u3a3 arbitra´rio:
P
\u2217\u21d2 awX\u2194 P \u2192 aY \u2208 R e Y \u2217\u21d2 wX pela definic¸a\u2dco de \u2217\u21d2
e Definic¸a\u2dco 26
\u2194 P \u2192 aY \u2208 R e X \u2208 \u3b4\u2c6({Y }, w) pela hipo´tese de induc¸a\u2dco
\u2194 Y \u2208 \u3b4(P, a) e X \u2208 \u3b4\u2c6({Y }, w) pela definic¸a\u2dco de \u3b4
\u2194 X \u2208 \u3b4\u2c6({P}, aw) pela definic¸a\u2dco de \u3b4\u2c6.
Finalmente, para provar que L(M) = L(G), sera´ mostrado que P
\u2217\u21d2 w \u2194 \u3b4\u2c6({P}, w)\u2229
F 6= \u2205. Sa\u2dco considerados dois casos:
Caso 1. w = \u3bb.
P
\u2217\u21d2 \u3bb\u2194 P \u2192 \u3bb \u2208 R pela definic¸a\u2dco de \u2217\u21d2 e Definic¸a\u2dco 26
\u2194 P \u2208 F e P 6= Z pela definic¸a\u2dco de F
\u2194 \u3b4\u2c6({P}, \u3bb) \u2208 F pela definic¸a\u2dco de \u3b4\u2c6
\u2194 \u3b4\u2c6({P}, \u3bb) \u2229 F 6= \u2205 pois |\u3b4\u2c6({P}, \u3bb)| = |{P}| = 1.
Caso 2. w = xa.
P
\u2217\u21d2 xa\u2194 [P \u2217\u21d2 xaX e X \u2192 \u3bb \u2208 R] ou
[P
\u2217\u21d2 xX e X \u2192 a \u2208 R] pela def. de \u2217\u21d2 e Definic¸a\u2dco 26
\u2194 [X \u2208 \u3b4\u2c6({P}, xa) e X \u2192 \u3bb \u2208 R] ou
[P
\u2217\u21d2 xX e X \u2192 a \u2208 R] por 2.4
\u2194 [X \u2208 \u3b4\u2c6({P}, xa) e X \u2192 \u3bb \u2208 R] ou
[X \u2208 \u3b4\u2c6({P}, x) e X \u2192 a \u2208 R] por 2.4
\u2194 [X \u2208 \u3b4\u2c6({P}, xa) e X \u2192 \u3bb \u2208 R] ou
[X \u2208 \u3b4\u2c6({P}, x) e Z \u2208 \u3b4(X, a)] pela definic¸a\u2dco de \u3b4
\u2194 [X \u2208 \u3b4\u2c6({P}, xa) e X \u2192 \u3bb \u2208 R] ou Z \u2208 \u3b4\u2c6({P}, xa)
pela definic¸a\u2dco de \u3b4\u2c6
\u2194 \u3b4\u2c6({P}, xa) \u2229 F 6= \u2205 pela Definic¸a\u2dco de F .
121
-
\ufffd\ufffd\ufffd\ufffdA
?
0
\ufffd\ufffd
?
0
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
Z
-1 B
\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd\ufffd
\ufffd\ufffd
?
1
Figura 2.35: AFN a partir de GR.
Pela construc¸a\u2dco apresentada na prova do Teorema 14, fica evidente que uma GR
pode ser vista quase que como uma forma linear de se apresentar um AFN: cada regra da
forma X \u2192 aY corresponde a uma transic¸a\u2dco Y \u2208 \u3b4(X, a), cada regra da forma X \u2192 a
corresponde a uma transic¸a\u2dco Z \u2208 \u3b4(X, a), onde Z e´ estado final no AFN, e cada regra
X \u2192 \u3bb corresponde a um estado final no AFN.
Exemplo 88 Seja a GR G = ({A,B}, {0, 1}, R,A), onde R e´ dado por:
A\u2192 0A|1B|0
B \u2192 1B|\u3bb
Um diagrama de estados para um AFN que reconhece a linguagem L(G) = 0\u2217(0 +
1+), constru´\u131do utilizando o me´todo visto na prova do Teorema 14 esta´ mostrado na
Figura 2.35.
Observe a correponde\u2c6ncia entre regras e transic¸o\u2dces:
Regras Transic¸o\u2dces Observac¸a\u2dco
A\u2192 0A A \u2208 \u3b4(A, 0)
A\u2192 1B B \u2208 \u3b4(A, 1)
A\u2192 0 Z \u2208 \u3b4(A, 0) Z e´ estado final
B \u2192 1B B \u2208 \u3b4(B, 1)
B \u2192 \u3bb B e´ estado final.
A seguir, mostra-se como construir uma GR que gera a linguagem reconhecida por
um AFN.
Teorema 15 Toda linguagem regular e´ gerada por grama´tica regular.
Prova
Seja um AFN M = (E,\u3a3, \u3b4, {i}, F )9. Uma GR que gera L(M) seria G = (E,\u3a3, R, i),
onde:
R = {e\u2192 ae\u2032 | e\u2032 \u2208 \u3b4(e, a)} \u222a {e\u2192 \u3bb | e \u2208 F}.
9Basta considerar AFN\u2019s com um u´nico estado inicial; afinal, qualquer linguagem regular e´ reconhecida
por um AFD, e um AFD e´ um AFN com um u´nico estado inicial.
122
Sera´ utilizado o seguinte lema, que pode ser provado por induc¸a\u2dco sobre |w| (veja o
exerc´\u131cio 5 no final da sec¸a\u2dco):
i
\u2217\u21d2 we se, e somente se, e \u2208 \u3b4\u2c6({i}, w) para todo e \u2208 E e w \u2208 \u3a3\u2217 (2.5)
Para mostrar que L(M) = L(G), sera´ provado que:
i
\u2217\u21d2 w se, e somente se, \u3b4\u2c6({i}, w) \u2229 F 6= \u2205 para todo w \u2208 \u3a3\u2217:
i
\u2217\u21d2 w\u2194 i \u2217\u21d2 we e e\u2192 \u3bb \u2208 R pela definic¸a\u2dco de R
\u2194 e \u2208 \u3b4\u2c6({i}, w) e e\u2192 \u3bb \u2208 Rpor 2.5
\u2194 e \u2208 \u3b4\u2c6({i}, w) e e \u2208 F pela definic¸a\u2dco de R
\u2194 \u3b4\u2c6({i}, w) \u2229 F 6= \u2205 pela definic¸a\u2dco de intersec¸a\u2dco.
A prova do Teorema 15 mostra que pode-se construir uma GR, que reconhece a
linguagem reconhecida por um AFN, que so´ tenha regras das formas X \u2192 aY e X \u2192 \u3bb.
Combinado com o resultado do Teorema 14, isto mostra que para toda linguagem regular
existe uma GR equivalente sem regras da forma X \u2192 a.
Exemplo 89 Uma GR, constru´\u131da de acordo com a prova do Teorema 15, que gera a
linguagem aceita pelo AFN cujo diagrama de estados esta´ mostrado na Figura 2.35, e´
({A,B,Z}, {0, 1}, R,A), onde R e´ dado por:
A\u2192 0A|0Z|1B
B \u2192 1B|\u3bb
Z \u2192 \u3bb
Exerc´\u131cios
1. Obtenha GR\u2019s para as seguintes linguagens sobre {0,1}:
(a) \u2205.
(b) {\u3bb}.
(c) O conjunto das palavras com tamanho mu´ltiplo de 3.
(d) O conjunto das palavras com um nu´mero par de 0\u2019s e um nu´mero par de 1\u2019s.
(e) O conjunto das palavras em que cada 0 e´ seguido imediatamente de, no m\u131´nimo,
dois 1\u2019s.
(f) O conjunto das palavras em que o ante-penu´ltiplo s´\u131mbolo e´ 1.
2. Obtenha um AFN que reconhec¸a a linguagem gerada pela GR do exemplo 87,
pa´gina 120, utilizando o me´todo da prova do Teorema 14.
3. Seja a GR G = ({P,A,B}, {a, b}, R, P ), onde R consta das regras:
123
P \u2192 aP |bP |aA
A\u2192 a|bB
B \u2192 bA
Construa, a partir de G, um AFN que aceite L(G).
4. Seja a linguagem L = {w \u2208 {0, 1}\u2217 | w tem nu´meros par de 0\u2019s e \u131´mpar de 1\u2019s}.
Obtenha um AFD para L. Utilizando o me´todo to Teorema 15, obtenha uma GR
que gere L.
5. Complete a prova do Teorema 15, provando o lema por induc¸a\u2dco sobre |w|:
i
\u2217\u21d2 we se, e somente se, e \u2208 \u3b4\u2c6({i}, w) para todo e \u2208 E e w \u2208 \u3a3\u2217.
6. Alguns autores definem uma grama´tica regular como sendo uma grama´tica em que
as regras sa\u2dco da forma X \u2192 xY e X \u2192 x, onde X e Y sa\u2dco varia´veis e x e´ uma
palavra de terminais. Mostre como obter uma GR equivalente a uma grama´tica
com regras desta forma.
7. Responda a`s seguintes perguntas, justificando suas respostas:
(a) Quantas regras, no m\u131´nimo, sa\u2dco necessa´rias para gerar uma linguagem infinita?
(b) Dada uma expressa\u2dco regular, e´ poss´\u131vel obter uma GR que gera a linguagem
denotada por ela?
(c) E´ poss´\u131vel gerar qualquer linguagem finita por meio de GR?
(d) Dada uma GR e´ poss´\u131vel obter uma outra GR equivalente em que a gerac¸a\u2dco
de qualquer palavra e´ determin´\u131stica (em qualquer passo da derivac¸a\u2dco existe
uma u´nica regra aplica´vel)?
8. Mostre que os seguintes problemas sa\u2dco decid´\u131veis, onde G1 e G2 sa\u2dco GR\u2019s quaisquer:
(a) L(G1)