Exercicios resolvidos de teoria dos automatos e linguagens formais

Prévia do material em texto

1
Universidade Estadual do Ceará
Centro de Ciências e Tecnologia
Curso de Ciência da Computação
Disciplina: Teoria dos Autômatos e Linguagens Formais
Professor: Edson Pessoa
Semestre Acadêmico 2009.2
Resolução do 2
a
NTI
Aluno: Neuton de Oliveira Braga Jr
E-mail: neutonjr2008@gmail.com
Fortaleza - CE
17 de janeiro de 2010
2
Questões e Respostas
Questão 1
Seja G a gramática:
S → ASB | λ (I)
A→ aAb | λ (II)
B → bBa | ba (III)
a) Dê a derivação mais à esquerda de aabbba.
Resposta:
S ⇒ ASB por (I)
⇒ aAbSB por (II)
⇒ aaAbbSB por (II)
⇒ aabbSB por (II)
⇒ aabbB por (I)
⇒ aabbba por (III)
b) Dê a derivação mais à direita de abaabbbabbaa.
Resposta:
S ⇒ ASB por (I)
⇒ ASbBa por (III)
⇒ ASbbaa por (III)
⇒ AASBbbaa por (I)
⇒ AASbabbaa por (III)
⇒ AAbabbaa por (I)
⇒ AaAbbabbaa por (II)
⇒ AaaAbbbabbaa por (II)
⇒ Aaabbbabbaa por (II)
⇒ aAbaabbbabbaa por (II)
⇒ abaabbbabbaa por (II)
c) Construa as árvores de derivação dos itens a e b.
3
4
Resposta:
Árvore de derivação Ordem dos Filhos
S
ASB
aAbba
aaAbbba
aabbba
S
ASB
aAbASBbBa
abaAbbabbaa
abaaAbbbabbaa
abaabbbabbaa
d) Use a notação de conjunto para definir L(G).
Resposta:
L(G) = {(aibi)m(bjaj)n | m, i ≥ 0 e n, j > 0}
Por exemplo: (a2b2)2(ab)3ba ∈ L(G).
Questão 2
Dada gramática G seguinte, use a notação de conjunto para definir a linguagem gerada pela
mesma.
S → aSbb | A
A→ cA | c
Resposta:
L(G) = {amcnb2m | m ≥ 0 e n > 0}
Por exemplo: (a20)c(b)40 ∈ L(G).
Questão 3
Construa uma gramática G sobre Σ = {a, b, c} cuja linguagem é definida como L(G) =
{ambnci | m > n+ i}.
Resposta:
G : S → aS | aC
B → aBb | λ
C → B | aCc | λ
5
Questão 4
Seja G a gramática:
S → aSaa | B (I)
B → bbBdd | C (II)
C → bd (III)
a) Qual a linguagem gerada por G?
Resposta:
L(G) = {amb2n+1d2n+1a2m | m,n ≥ 0}
b) Prove que L(G) é o conjunto do item a).
Resposta:
Seja o conjunto de palavras X = {amb2n+1d2n+1a2m | m,n > 0} sobre o alfabeto Σ =
{a, b, d}. Para provar que L(G) = X, inicialmente provaremos que X ⊆ L(G) e, depois,
L(G) ⊆ X:
P1) X ⊆ L(G):
Essa prova é feita ao se mostrar que toda palavra w ∈ X é derivável de G. A idéia é se
encontrar um padrão de derivação que se aplique a qualquer palavra w ∈ X.
Assim, se w ∈ X então w tem a forma amb2n+1d2n+1a2m, para m,n ≥ 0, e pode ser obtida
usando-se as seguintes derivações:
S ⇒ (a)mS(aa)m por (I) aplicada 'm' vezes, sendo (m ≥ 0)
⇒ (a)mB(aa)m por (I)
⇒ (a)m(bb)nB(dd)n(aa)m por (II) aplicada 'n' vezes, sendo (n ≥ 0)
⇒ (a)m(bb)nC(dd)n(aa)m por (II)
⇒ (a)m(bb)nbd(dd)n(aa)m por (III)
⇒ amb2n+1d2n+1a2m
P2) L(G) ⊆ X:
Essa prova é feita ao se mostrar que toda palavra w derivável de G pertence a X. Para
isso, caracterizaremos uma palavra u ∈ X por meio de algumas relações, e, por conseguinte,
mostraremos que toda sentença obtida de G também satisfaz essas relações.
Seja nu(c) o número de vezes que o símbolo c aparece numa palavra u. Podemos caracterizar
as palavras u ∈ X por meio de algumas relações. São elas:
1. Quanto ao número de símbolos da palavra u:
nu(a) = 3m, com m ≥ 0.
nu(b) = nu(d) = 2n+ 1, com n ≥ 0, ou seja, o número de b's e d's é ímpar.
2. Quanto à quantidade mínima de cada símbolo na palavra u. Duas situações:
Quando a ocorre: nu(a) ≥ 3 e nu(b) = nu(d) ≥ 1.
Quando a não ocorre: nu(b) = nu(d) ≥ 1.
6
3. Quanto à precedência, as ocorrências de a's precedem b's, que precedem d's e que, por sua
vez, precedem uma quantidade de a's correspondente ao dobro da quantidade do mesmo
símbolo no início da palavra.
E, também podemos caracterizar, quanto à quantidade de cada símbolo e quanto à pre-
cedência dos símbolos, uma forma sentencial qualquer, após aplicar cada uma das regras de
derivação (tabela abaixo). Para tanto, considere nu(c) o número de vezes que o símbolo c
aparece explicitamente na forma sentencial u antes da derivação, nu(c, C) o número de vezes
que o símbolo c aparece por meio da variável C na forma sentencial u antes da derivação, e,
n′u(c) o número de vezes que o símbolo c aparece na forma sentencial u depois de aplicada a
regra de derivação.
Regra n′u(a) n
′
u(b) n
′
u(d) Precedência
S → aSaa nu(a) + nu(a, S) + 3 nu(b) + nu(b, S) nu(d) + nu(d, S) A cada um a colocado
no início S, é colocado
dois a's no final
S → B nu(a) + nu(a,B) nu(b) + nu(b, B) nu(d) + nu(d,B) Mesma precedência da
variável B
B → bbBdd nu(a) + nu(a,B) nu(b) + nu(b, B) + 2 nu(d) + nu(d,B) + 2 Os b's precedem o B,
que precede os d's
B → C nu(a) + nu(a,C) nu(b) + nu(b, C) nu(d) + nu(d,C) Mesma precedência da
variável C
C → bd nu(a) nu(b) + 1 nu(d) + 1 b precede d
Diante disso, provaremos que as relações 1, 2 e 3 se mantém para as sentenças obtidas por
derivações a partir de S. Essa prova se dará por indução sobre o número de derivações partindo
de S, sendo na análise de uma forma sentencial específica sempre será considerada a sentença
mais próxima a ela obtida pela derivação das variáveis da forma sentencial, um número mínimo
de vezes, para obter apenas símbolos terminais. Assim, temos:
Variável Sentença mais próxima n′u(a) n
′
u(b) n
′
u(d)
C C ⇒ bd 0 1 1
B B ⇒ C
⇒ bd 0 1 1
S S ⇒ B
⇒ C
⇒ bd 0 1 1
Desse modo, a indução é feita da seguinte forma:
Base: Para uma única derivação, temos dois casos:
Regra n′u(a) n
′
u(b) n
′
u(d) Sentença mais próxima
S → aSaa 0 + 0 + 3 = 3 0 + 1 = 1 0 + 1 = 1 abdaa
S → B 0 + 0 = 0 0 + 1 = 1 0 + 1 = 1 bd
Assim:
Relações
Regras
S → aSaa S → B
u = abdaa u = bd
1 nu(a) = 3 = 3 ∗ 1 nu(a) = 0 = 3 ∗ 0
nu(b) = nu(d) = 1 = 2 ∗ 0 + 1 nu(b) = nu(d) = 1 = 2 ∗ 0 + 1
2 nu(a) = 3 ≥ 3 nu(b) = nu(d) = 1 ≥ 1
nu(b) = nu(d) = 1 ≥ 1
3 a precede b que precede d que precede dois a's b precede d
Logo, as relações 1, 2 e 3 são válidas para a base.
7
Hipótese: Suponha que as relações 1, 2 e 3 são válidas na análise para todas as formas
sentenciais u obtidas da derivação em n > 0 passos. Assim, seja iu, ju e ku o número de vezes
que as variáveis S, B e C, respectivamente, aparecem em u, então n′u(a), n
′
u(b) e n
′
u(d) são
dados por:
n′u(a) = nu(a) + iu.nu(a, S) + ju.nu(a,B) + ku.nu(a, C) = nu(a) = 3x, com x ≥ 0
n′u(b) = nu(b) + iu.nu(b, S) + ju.nu(b, B) + ku.nu(b, C) = nu(b) + iu + ju + ku = 2y + 1, com y ≥ 0
n′u(d) = nu(d) + iu.nu(d, S) + ju.nu(d,B) + ku.nu(d, C) = nu(d) + iu + ju + ku = 2y + 1, com y ≥ 0
Indução: Seja u e w formas sentenciais derivadas após, respectivamente, n e (n+1) passos:
S
n+1⇒ w
S
n⇒ u⇒ w
Devemos provar que as relações 1, 2 e 3 se aplicam a w.
Partindo da hipótese de indução, podemos encontrar a seguinte tabela com valores impor-
tantes relacionados com a palavra w, especialmente n′w(a), n
′
w(b) e n
′
w(d):
Regra nw(a) nw(b) nw(d) iw jw kw n′w(a) n
′
w(b) n
′
w(d)
S → aSaa nu(a) + 3 nu(b) nu(d) iu ju ku n′u(a) + 3 n′u(b) n′u(d)
S → B nu(a) nu(b) nu(d) iu − 1 ju + 1 ku n′u(a) n′u(b) n′u(d)
B → bbBdd nu(a) nu(b) + 2 nu(d) + 2 iu ju ku n′u(a) n′u(b) + 2 n′u(d) + 2
B → C nu(a) nu(b) nu(d) iu ju − 1 ku + 1 n′u(a) n′u(b) n′u(d)
C → bd nu(a) nu(b) + 1 nu(d) + 1 iu ju ku − 1 n′u(a) n′u(b) n′u(d)
Com isso, percebe-se que todos os valores n′w(a), n
′
w(b) e n
′
w(d) encontrados satisfazem a
relação 1.
As relações 2 e 3 podem ser também facilmente verificadas. Logo, L(G) ⊆ X.
Assim, por P1) e P2), temos que L(G) = X.
Questão 5
Seja M o autômato finito determinístico abaixo:
M δ a b
> q0 q0 q1
q1 q2 q1
< q2 q2 q0
a) Dê o diagrama do estado de M.
Resposta
8
b) Exiba as computações de M para as palavras abaa, bbbabb, bababa e bbbaa.
Resposta
[q0, abaa] ` [q0, baa] [q0, bbbabb] ` [q1, bbabb]
[q1, aa] [q1, babb]
[q2, a] [q1, abb]
[q2, λ] [q2, bb]
[q0, b]
[q1, λ]
[q0, bababa] ` [q1, ababa] [q0, bbbaa] ` [q1, bbaa]
[q2, baba] [q1, baa]
[q0, aba] [q1, aa][q0, ba] [q2, a]
[q1, a] [q2, λ]
[q2, λ]
c) Quais as palavras do item b que são aceitas por M?
Resposta
Somente as palavras abaa, bababa e bbbaa.
d) Dê a expressão regular de L(M)
Resposta
ER = a∗bb∗aa∗(ba∗bb∗aa∗)∗
Questão 6
Seja M um DAF cujo diagrama de estados é dado por:
9
a) Construa a tabela de transição para M.
Resposta:
M δ a b
> q0 q1 q0
q1 q1 qa
< qa q0 q1
b) Quais, dentre as palavras baba, baab, abab e abaaab não são aceitas por M?
Resposta:
[q0, baba] ` [q0, aba] [q0, baab] ` [q0, aab]
[q1, ba] [q1, ab]
[qa, a] [q1, b]
[q0, λ] [qa, λ]
[q0, abab] ` [q1, bab] [q0, abaaab] ` [q1, baaab]
[qa, ab] [qa, aaab]
[q0, b] [q0, aab]
[q0, λ] [q1, ab]
[q1, b]
[qa, λ]
Apenas as palavras baba e abab não são aceitas por M.
c) Dê a ER para L(M).
Resposta:
ER = b∗aa∗b((ba∗b)∗ + (ab∗aa∗b)∗)∗
Questão 7
Dê um diagrama de estados para o DAF que aceita as seguintes linguagens.
a) (ab)∗ba
Resposta:
b) (ab∗a)∗
10
Resposta: