Prova 1 e sua Solução - Universidade Federal de Uberlândia

Universidade Federal de Uberlândia
Bacharelado em Ciência da Computação
1a Prova de LFA - 23/10/2003
NOME :
NÚMERO :
VALOR DA PROVA : 100 PONTOS
NOTA =
Resolver as questões logo após o enunciado das mesmas, se preciso utilizando
o verso da página.
Questão 1 (valor = 30 pontos) Considere a seguinte gramática :
S
S
A
B
A
B
A
B
→
→
→
→
→
→
→
→
bA
aB
a
b
aS
bS
bAA
aBB
1. (25 pontos) Mostre que esta gramática é ambı́gua.
Solução
Uma gramática é ambı́gua se existe uma palavra que é possı́vel ser gerada pelas
regras da gramática, através de duas árvores de derivação distintas.
Considere a seguinte palavra w = bbaaba. Esta palavra pode ser gerada alternativamente pelas duas árvores de derivação descritas abaixo. Logo, esta gramática é
ambı́gua.
S
S
b
b
A
b
A
a
A
S
a
a
B
b
A
b
A
a
A
a
S
b
A
a
2. (5 pontos) A linguagem gerada por esta gramática é o conjunto das palavras contendo igual quantidade de a0 s e de b0 s. A partir do item anterior, é possı́vel concluir
que esta linguagem é ambı́gua ? Justifique sua resposta.
Solução
Não. Uma linguagem é ambigua se TODA gramática que a gera é ambigua. O fato
de EXISTIR UMA gramática que a gera que é ambigua, não significa que TODA
gramática que a gera é ambigua.
Questão 2 (valor = 30 pontos) : Considere a linguagem sobre o alfabeto Σ = {0, 1} :
L = {w1 xw2 | tamanho de w1 é o dobro do tamanho de w2 e x ∈ {0, 1}}
Dê uma gramática gerando esta linguagem. Dê argumentos que comprovem que a
linguagem gerada por esta gramática corresponde exatamente à linguagem L. Diga a que
tipo pertence esta gramática.
Solução
Considere a seguinte gramática :
S
S
S
S
S
S
S
S
S
S
→
→
→
→
→
→
→
→
→
→
01S0
01S1
00S0
00S1
11S0
11S1
10S0
10S1
0
1
Trata-se de uma gramática livre do contexto (tipo 2), pois do lado esquerdo das regras
só aparecem strings constituidos de um única variável. Vamos mostrar que a linguagem
gerada por esta gramática (L(G)) é exatamente a linguagem L.
1. L(G) ⊆ L
Seja w ∈ L(G). Então, temos 2 casos a considerar :
(a) w é gerada com um único passo de derivação. Neste caso, w = 0 ou w = 1. É
claro que w ∈ L, pois w = ²0² ou w = ²1² e tamanho de ² = 0 = 2*0 = dobro
do tamanho de ².
(b) w é gerada com mais de um passo de derivação. Então existem strings α1 , α2 , ..., αm ,
m ≥ 1, tais que :
S → α1 → α2 → αm → w
Mostremos por indução sobre m a seguinte asserção P(m)
P(m) = “Seja uma derivação derivação qualquer :
S → α1 → α2 → αm → α
onde α é um string qualquer. Então αm = w1 Sw2 , onde tamanho de w1 =
2*(tamanho de w2 )”.
Uma vez mostrado que P(m) é verdadeiro para todo m, podemos concluir que
w (uma palavra só contendo terminais) está em L, pois w só pode ser obtida a
partir de αm aplicando-se uma das duas últimas regras de G (as regras levando
em terminais), e αm tem a forma w1 Sw2 , onde tamanho de w1 = 2 e tamanho
de w2 = 1.
Demonstração de que P(m) é verdadeiro para todo m ≥ 1:
Base da indução : P(∞) é verdadeiro. Seja S → α1 → α. Logo a primeira
regra só pode ser uma das 8 primeiras regras, o que produz um string w1 Sw2 ,
onde tamanho de w1 = 2 e tamanho de w2 = 1.
Hipótese de indução : Suponha P(m) verdadeiro e provemos P(m + 1). Supomos então uma derivação de um string α qualquer :
S → α1 → α2 → αm → αm+1 → α
Ora, a sequência S → α1 → α2 → αm → αm+1 constitui uma derivação do string
αm+1 com m passos. Logo, pela hipótese de indução, podemos concluir que αm é
da forma w1 Sw2 , onde tamanho de w1 é o dobro do tamanho de w2 . Logo, αm+1
= w1 u1 Su2 w2 , onde tamanho de u1 = 2 e tamanho de u2 = 1. Logo : tamanho de
w1 u1 = soma dos tamanhos de w1 e u1 = dobro do tamanho da soma dos tamanhos
de u2 e w2 = tamanho de w2 u2 .
2. L ⊆ L(G).
Seja w ∈ L. Se w = 0 ou w = 1, é claro que podemos gerar w aplicando-se uma
das duas últimas regras. Supomos então que w 6= 0 e w 6= 1. Então w = w1 0w2
ou w = w1 1w2 , onde tamanho de w1 = dobro do tamanho de w2 , e tamanho de w2
≥ 1. Vamos demonstrar a seguinte asserção P(n) por indução sobre n :
P(n) : Se u é um string qualquer do tipo u = u1 Su2 , onde u1 e u2 são palavras
quaisquer tais que tamanho de u1 = 2n e n = tamanho de u2 ≥ 1, então podemos
gerar o string u a partir de S aplicando-se regras da gramática G.
Base da indução : n = 1. Neste caso u1 = 00, ou 01, ou 11 ou 10 e w2 = 1 ou
0. Então, obviamente, u = u1 Su2 é gerada aplicando-se uma vez uma das oito
primeiras regras, dependendo do caso.
Hipótese de indução : Suponha P(n) verdadeiro.
Vamos mostrar que P(n + 1) é verdadeiro. Seja u = u1 Su2 , onde tamanho de u1 =
2(n+1) e n + 1 = tamanho de u2 . Então :
u = b1 b01 b2 b02 ...bn b0n bn+1 b0n+1 San+1 an ...a1
(obviamente estamos supondo u1 = b1 b01 b2 b02 ...bn b0n bn+1 b0n+1 e u2 = an+1 an ...a1 .)
Considere o string u0 = b1 b01 b2 b02 ...bn b0n San ...a1 . Por hipótese de indução, podemos
concluir que u0 pode ser gerado aplicando-se as regras da gramática G a partir de
S:
S → .... → b1 b01 b2 b02 ...bn b0n San ...a1
Consideremos a regra da gramática S → bn+1 b0n+1 San+1 .
Então, aplicando-se esta regra em b1 b01 b2 b02 ...bn b0n San ...a1 obtemos uma derivação de
u a partir de S.
Questão 3 (valor = 30 pontos) : Considere a linguagem sobre o alfabeto Σ = {0, 1}
constituı́da das palavras do tipo w1 w2 tais que w1 contém um número par de zeros e um
número par de uns e w2 é um bloco de zeros de tamanho impar. Por exemplo, a palavra
w = 0101000 pertence a esta linguagem, mas w0 = 110000 não pertence.
1. (valor = 20 pontos) Utilizando o algoritmo de concatenação de autômatos,
construa um autômato que reconheça exatamente esta linguagem. Não serão aceitas
soluções que não utilizem o algoritmo de concatenação de autômatos.
Solução
O autômato que reconhece a linguagem constituida de palavras com um número par
de zeros e um número par de uns é o seguinte :
0
q1
q2
0
1
1
1
1
0
q4
q3
0
Tal autômato foi visto com todos os detalhes em aula e na página do curso existe
um material contendo a demonstração rigorosa por indução mútua, de que este
autômato reconhece exatamente a linguagem pedida. Tal material está disponivel
para estudo já há mais de um mes !!
O autômato que reconhece a linguagem sobre o alfabeto {0,1} contendo somente as
palavras constituı́das de blocos de zeros de comprimento impar é o seguinte :
0
q00
q10
0
1
1
1
q20
0
Uma vez que estes dois autômatos são deterministas, podemos aplicar o algoritmo
de concatenação de autômatos para produzir o autômato seguinte que reconhece
exatamente a linguagem pedida :
0
0
q1
q2
0
q00
0
q10
0
1
1
1
1
1
0
q4
1
q3
0
q20
1
0
1
2. (valor = 5 pontos) Construa uma gramática regular correspondente a este autômato.
Solução
Utilizando o algoritmo que transforma autômato em gramática regular, obtemos a
seguinte gramática gerando a linguagem pedida :
q1
q1
q2
q2
q3
q3
q4
q4
q1
q1
q1
q10
q10
q00
q00
q20
q20
q00
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→
0q1
1q4
0q1
1q3
0q2
1q2
1q1
0q3
0
0q10
1q20
0q00
1q20
0q10
1q20
1q20
0q20
0
3. (valor = 5 pontos) Construa uma expressão regular correspondente a este autômato.
Solução
A expressão regular correspondente a este autômato é dada por :
e1 e2
onde e1 é a expressão correspondente à linguagem L1 = palavras w1 contendo um
número par de zeros e um número par de uns e e2 é a expressão correspondente ao
conjunto das palavras constituı́das de um bloco de zeros de tamanho impar.
(a) Afirmamos que e2 = 0(00)∗ . Prova : De fato, se w é uma palavra da linguagem
de e2 então w = 0w1 ...wm , onde cada wi = 00. Logo, o tamanho de w = 1 + 2m
(um número impar). Reciprocamente, se w é uma palavra constituida de um
bloco de zeros de tamanho impar, então w = w1 ...wn , onde cada wi = 0 e n é
impar. Neste caso, n = 1 ou n = 2m + 1, para algum m ≥ 1. Logo, w = 0 ou
w = 0u1 ...um , onde cada ui = 00. Portanto, w está na linguagem da expressão
0(00)∗ .
(b) Vamos utilizar o algoritmo que transforma autômato em expressão regular a
k
fim de exibir a expressão e1 . Vamos denotar por rij
as expressões regulares
k
correspondentes às linguagens Rij . Então, temos :
4
3
3
3 ∗ 3
e1 = r11
= r11
+ r14
(r44
) r41
Nı́vel 3
3
r11
3
r14
3
r44
3
r41
=
=
=
=
2
2
2 ∗ 2
r11
+ r13
(r33
) r31
2
2
2 ∗ 2
r14 + r13 (r33 ) r34
2
2
2 ∗ 2
r44
+ r43
(r33
) r34
2
2
2 ∗ 2
r41 + r43 (r33 ) r31
2
r14
2
r13
2
r33
2
r34
2
r44
2
r43
2
r41
2
r31
2
r11
=
=
=
=
=
=
=
=
=
1
1
1 ∗ 1
r14
+ r12
(r22
) r24
1
1
1 ∗ 1
r13 + r12 (r22 ) r23
1
1
1 ∗ 1
r33
+ r32
(r22
) r23
1
1
1 ∗ 1
r34 + r32 (r22 ) r24
1 ∗ 1
1
1
) r24
(r22
+ r42
r44
1
1
1 ∗ 1
r43 + r42 (r22 ) r23
1
1
1 ∗ 1
r41
+ r42
(r22
) r21
1
1
1 ∗ 1
r31 + r32 (r22 ) r21
1
1
1 ∗ 1
r11
+ r12
(r22
) r21
Nı́vel 2
Nı́vel 1
1
r14
1
r12
1
r22
1
r24
1
r13
1
r33
1
r32
1
r23
1
r34
1
r44
1
r42
1
r43
1
r41
1
r21
1
r31
1
r11
0
0
0 ∗ 0
r14
+ r11
(r11
) r14
0
0
0 ∗ 0
r12 + r11 (r11 ) r12
0
0
0 ∗ 0
r22
+ r21
(r11
) r12
0
0
0 ∗ 0
r24 + r21 (r11 ) r14
0
0
0 ∗ 0
r13
+ r11
(r11
) r13
0
0
0 ∗ 0
r33 + r31 (r11 ) r13
0
0
0 ∗ 0
r32
+ r31
(r11
) r12
0
0
0 ∗ 0
r23 + r21 (r11 ) r13
0
0
0 ∗ 0
r34
+ r31
(r11
) r14
0
0
0 ∗ 0
r44 + r41 (r11 ) r14
0
0
0 ∗ 0
r42
+ r41
(r11
) r12
0
0
0 ∗ 0
r43
+ r41
(r11
) r13
0
0
0 ∗ 0
r41 + r41 (r11 ) r11
0
0
0 ∗ 0
r21
+ r21
(r11
) r11
0
0
0 ∗ 0
r31 + r31 (r11 ) r11
0
0
0 ∗ 0
r11
+ r11
(r11
) r11
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=1
=0
= ² + 00
= 01
=∅
=∅
=1
=1
=0
= ² + 11
= 10
=0
=1
=0
=∅
=²
Substituindo-se os valores acima nas expressões do nı́vel 2, obtemos :
Nı́vel 2 (após as substituições)
2
r14
2
r13
2
r33
2
r34
2
r44
2
r43
2
r41
2
r31
2
r11
=
=
=
=
=
=
=
=
=
1 + 0(² + 00)∗ 01
0(² + 00)∗ 1
1(² + 00)∗ 1
0 + 1(² + 00)∗ 01
² + 11 + 10(² + 00)∗ 01
0 + 10(² + 00)∗ 1
1 + 10(² + 00)∗ 0
1(² + 00)∗ 0
² + 0(² + 00)∗ 0
Substituindo-se os valores acima nas expressões do nı́vel 3, obtemos :
Nı́vel 3 (após as substituições)
3
r11
3
r14
3
r44
3
r41
= ² + 0(² + 00)∗ 0 + (0(² + 00)∗ 1)(1(² + 00)∗ 1)∗ 1(² + 00)∗ 0
= 1 + 0(² + 00)∗ 01 + 0(² + 00)∗ 1(1(² + 00)∗ 1)∗ (0 + 1(² + 00)∗ 01)
= ² + 11 + 10(² + 00)∗ 01 + 0 + 10(² + 00)∗ 1(1(² + 00)∗ 1)∗ (0 + 1(² + 00)∗ 01)
= (1 + 10(² + 00)∗ 0) + (0 + 10(² + 00)∗ 1)(1(² + 00)∗ 1)∗ 1(² + 00)∗ 0
3
3
3 ∗ 3
Substituindo-se estas expressões na expressão inicial e1 = r11
+ r14
(r44
) r41 ,
obtemos a expressão regular correspondente à linguagem L1 .
Questão 4 (valor = 10 pontos) : Diga se é verdadeiro ou falso e justifique sua resposta.
Atenção : respostas sem justificativas, só com as indicações Falso/Verdadeiro,
não serão consideradas !!.
1. (5 pontos) Uma linguagem reconhecida por um autômato é recursiva.
Solução
Verdadeiro. O autômato é um algoritmo que decide se uma palavra qualquer
pertence à linguagem : se ao percorrer a palavra, chegamos num estado final, o
autômato permite concluir que a palavra está na linguagem. Caso ao percorrer a
palavra, chega-se a um estado que não é final, o autômato permite concluir que a
palavra não está na linguagem.
2. (5 pontos) Uma linguagem gerada por uma gramática não é recursiva.
Solução
Falso. Considere uma linguagem gerada por uma gramática regular. Tal linguagem
pode ser reconhecida por um autômato. Logo, pelo item anterior ela é recursiva.