MESTRADO INTEGRADO EM ENGENHARIA INFORMÁTICA E COMPUTAÇÃO | 2º ANO EIC0022 | TEORIA DA COMPUTAÇÃO | 2012/2013 – 1º SEMESTRE

Prova sem consulta. Duração: 1h30m. Mini-Teste

Nome: __________________________________________________ Número: _______________

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 1 / 6

Nota: As respostas erradas têm cotação negativa. Numa pergunta com 4 alternativas, uma resposta errada tem uma

cotação negativa igual a 1/3 da cotação da pergunta. Numa pergunta com 2 alternativas, a resposta errada tem uma

cotação negativa igual à cotação da pergunta. As perguntas não respondidas têm cotação 0.

1. Prova por Indução

Pretende-se provar que o autómato abaixo aceita cadeias no alfabeto ∑={0,1} com um número ímpar

de 1’s. Assuma como provado que δ^(A, w)=A sempre que w tenha um número par de 1’s:

1.1 [0,8val] Uma forma de efectuar essa prova é:

usar indução em |w| para provar que δ^(A, w) = A se e só se w tem um número ímpar de 1's

usar indução em |w| para provar que δ^(A, w) = B se e só se w tem um número par de 1's

usar indução em |w| para provar que δ^(A, w) = B se e só se w tem um número ímpar de 1's

provar que a expressão regular equivalente não contém (11)*

1.2 [0,8] Para o passo base, temos de mostrar que:

para |w| = 0, w é uma cadeia vazia com número par de 1's (zero 1's) e δ^(A, w) = A

para |w| = 0, w é uma cadeia vazia com número ímpar de 1's (zero 1's) e δ^(A, w) = B.

para |w| = 1, w é uma cadeia com número par de 1's e δ^(A, w) = B

para |w| = 1, w é uma cadeia com número ímpar de 1's e δ^(A, w) = B

1.3 [0,8] No passo indutivo podemos efectuar uma decomposição de w em za (w = za com |z|<|w| e |a|

= 1), e verificar que para qualquer w de comprimento k:

(a) para a = 0, se w tem um número par de 1’s, z tem um número par de 1’s e como δ^(A, z) =

A, logo δ^(A, z0) = A

(b) para a = 0, se w tem um número ímpar de 1’s, z tem um número ímpar de 1’s e pela hipótese

de indução δ^(A, z) = B, logo δ^(A, z0) = B

(c) para a = 1, se w tiver um número ímpar de 1’s, z tem um número par de 1’s e pela hipótese

de indução δ^(A, z) = A, logo δ^(A, z1) = B

(b) e (c) têm de ser verificadas

2. Autómatos Finitos Deterministas (DFA’s)

Considere o seguinte DFA:

2.1 [0,8] Qual o estado onde o DFA se encontra após processar a subcadeia 010011001: a partir do

estado A, do estado B, e do estado C?

C se considerarmos que inicia em C; A ou B quando inicia em B e A, respectivamente;

A ou B ou C dependendo do estado em que inicia;

C independentemente do estado em que inicia;

Não é possível saber qual o estado em que o autómato de encontra;

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 2 / 6

2.2 [0,8] Qual é a linguagem aceite pelo DFA?

Todas as cadeias de 0’s e 1’s que não contêm nem 1’s nem 0’s consecutivos;

Todas as cadeias de 0’s e 1’s que não contêm 1’s consecutivos e são terminadas em 10;

Todas as cadeias de 0’s e 1’s que não contêm 1’s consecutivos;

Todas as cadeias de 0’s e 1’s;

2.3 [0,8] Considerando ={0,1}, indique qual dos seguintes DFAs representa o complemento da

linguagem definida pelo DFA anterior:

2.4 [0,8] Qual dos seguintes autómatos aceita todas as representações binárias de números inteiros

divisíveis por 3, podendo ignorar os 0’s à esquerda do primeiro 1. Nota: zero é divisível por qualquer

número diferente de zero.

3. Minimização de Autómatos

Considere a seguinte tabela de transição de estados de um DFA com 10 estados e a respectiva tabela

de estados distinguíveis (X indica que os dois estados não são equivalentes).

0 1

1 2

2 3

* 3 4

* 4 5

5 6

6 7

7 8

* 8 9

* 9 0 1 2 3 4 5 6 7 8

b

8

3

5

5

5

9

1

7

a

1

8

4

7

6

2

3 2

2 4

5 8

3.1 [0,8] As equivalências que devem existir para que os dois estados 0 e 7 sejam equivalentes são:

1 equivalente a 6, e 9 equivalente a 5

1 equivalente a 9, e 6 equivalente a 5

0 equivalente a 7, 1 equivalente a 6, e 9 equivalente a 5

Os estados 0 e 7 não podem ser equivalentes (um é estado inicial e o outro não)

Nome: __________________________________________________ Número: _______________

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 3 / 6

3.2 [0,8] As igualdades que devem existir para que os dois estados 7 e 8 sejam equivalentes são:

6 equivalente a 5, e 1 equivalente a 3

6 equivalente a 1, e 5 equivalente a 3

7 equivalente a 8, 6 equivalente a 1, e 5 = 3

Os estados 7 e 8 não podem ser equivalentes (um é estado de aceitação e o outro não)

3.3 [0,8] O DFA mínimo equivalente ao dado tem:

3 estados (1 de aceitação e 2 de não aceitação)

5 estados (2 de aceitação e 3 de não aceitação)

3 estados (2 de aceitação e 1 de não aceitação)

5 estados (3 de aceitação e 2 de não aceitação)

3.4 [0,8] Um dos estados do DFA mínimo equivalente é o estado {3,4,8}, sendo assim:

δ({3,4,8}, a) = {1}, e δ({3,4,8}, b) = {3}

δ({3,4,8}, a) = {1,2}, e δ({3,4,8}, b) = {3,4,8}

δ({3,4,8}, a) = {1,2,5}, e δ({3,4,8}, b) = {3,4,8}

δ({3}, a) = {1,2,3}, e δ({3}, b) = {3,4,8}

4. Autómatos Finitos Não-Deterministas (NFA’s)

Considere a seguinte tabela de transição de estados de um NFA:

p

q

r

* s

* t

1

{p}

0

{p,q}

{r,s} {t}

{p,r} {t}

Ø Ø

Ø Ø

4.1 [0,8] O DFA equivalente é:

Nenhum dos apresentados.

5. Expressões regulares

5.1 [0,8] Indique qual das seguintes expressões regulares representa todas as cadeias sobre o alfabeto

{a,b} com um número ímpar de a’s:

b*ab*(ab*a)*b*

b*a(b*ab*ab*)*

b*a(b*ab*a)*b*

as 3 expressões regulares apresentadas definem a linguagem constituída por essas cadeias

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 4 / 6

5.2 [0,8] Indique qual das seguintes expressões regulares define a mesma linguagem que L((b +

ab*a)*ab*):

b*ab*(ab*a)*b*

b*a(b*ab*ab*)*

b*a(b*ab*a)*b*

as 3 expressões regulares apresentadas definem essa linguagem

5.3 [0,8] Indique qual das seguintes expressões regulares representa cadeias sobre o alfabeto {a,b}

terminadas em b e não contendo a cadeia aa:

a(b + ab)*b

(b + ab)*(b + ab)

(a + ab)*b

(a + ab)*(a + ab)

6. Conversão de Autómatos em Expressões Regulares

Considere o seguinte DFA:

6.1 [0,8] Se considerarmos o método de construção de caminhos (Rij(k) = Rij

(k-1) + Rik(k-1) (Rkk

(k-1))* Rkj(k-

1), em que 0 k N e 1 i, j N) para determinar uma expressão regular correspondente ao DFA

obtemos, para k=0:

R(0)11=a+, R(0)

22=, R(0)

33=, R(0)

12=b, R(0)13=, R(0)

21=a, R(0)23=b, R(0)

31=a, R(0)32=b;

R(0)11=a, R(0)

22=, R(0)33=, R(0)

12=b, R(0)13=, R(0)

21=a, R(0)23=b, R(0)

31=a, R(0)32=b;

R(0)11=bba, R(0)

22=bab, R(0)33=abb, R(0)

12=b, R(0)13=bb, R(0)

21=ba, R(0)23=b, R(0)

31=a, R(0)32=ab;

Nenhuma das alíneas apresentadas é a correta.

6.2 [0,8] Supondo R(1)11= a*, R(1)

21 = R(1)31= aa*, R(1)

12 = R(1)32 = a*b, R(1)

22 = + aa*b, R(1)13 = ,

R(1)23 = b e R(1)

33= , a expressão regular para R(2)31 pode ser dada por:

aa* + (a*b)( + aa*b)*(aa*)

aa* + a*b(aa*b)*aa*

aa* + a*baa*(baa*)*

todas as expressões apresentadas estão corretas

6.3 [0,8] A expressão regular obtida pela construção de caminhos é dada por:

R(3)11 + R(3)

22;

R(3)11 + R(3)

12;

R(3)11

R(3)12;

6.4 [0,8] Aplicando agora o método de eliminação de estados, se for eliminado o estado 3 qual é o

autómato resultante?

Nome: __________________________________________________ Número: _______________

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 5 / 6

6.5 [0,8] A expressão regular que define a linguagem do autómato é dada por:

(a + b(ba))*b*

(a + b*(a + ba))*

(a + b(bb)*(a + ba))*b(bb)*

(a + b(bb)*(a + ba))*( + b(bb)*)

7. Conversão de Expressões Regulares em -NFAs

7.1 [0,8] Considere a expressão regular ((aa + b)*(aba)*bab)*. Indique qual dos autómatos seguintes

pode ser obtido a partir desta expressão regular:

8. Linguagens Regulares

8.1 [4val] Indique se cada uma das seguintes afirmações é verdadeira ou falsa:

V F

Uma linguagem constituída por um subconjunto de palavras de uma linguagem regular é sempre

uma linguagem regular.

Dadas duas expressões regulares quaisquer, conseguimos provar sempre se definem a mesma

linguagem regular ou não.

João M. P. Cardoso / Mário Cordeiro / João Jacob / Luís Teófilo 21/11/2012 | PÁG 6 / 6

A linguagem L={0n0n | n ≥ 0} é uma linguagem regular.

A linguagem resultante da aplicação do operador a duas linguagens regulares é sempre uma

linguagem regular. O operador é definido do seguinte modo: dadas duas linguagens L1 ={abc,

ca} e L2={ab, de}, L1 L2 = {abcab, abcde, caab, cade, ababc, abca, deabc, deca}.

A interseção de uma linguagem não regular com uma linguagem regular nunca pode ser uma

linguagem regular.

O fecho L* de uma linguagem regular L forma sempre uma nova linguagem.

A linguagem constituída pelas palavras formadas com o alfabeto ∑ = {a, b, c} que contêm um

número de par de a’s, b’s e c’s, ou um número ímpar de a’s, b’s e c’s é uma linguagem regular.

L(a*b*) L((a+b)*) = L(a*b*), e L(a*b*) L((a+b)*) = L((a+b)*)

L((a+b)*) 1L = L(a*bb*a(a+b)*), em que L1 = {anbm | n,m ≥ 0}

Qualquer que seja a linguagem regular existe sempre uma expressão regular que a representa.