Prova 1 e sua Solução - Universidade Federal de Uberlândia
Transcrição
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.