Baixe o app para aproveitar ainda mais
Prévia do material em texto
Universidade Federal de Sergipe – CCET – Departamento de Computação Linguagens Formais e Computabilidade - Turma 01 - 2020.2 – Primeira Prova Professor: Breno Piva Ribeiro Aluno: 1) Assinale a alternativa que contém a descrição formal de um Autômato Finito Determinístico que reconhece a linguagem {w | w termina com 110}, o alfabeto é {0, 1}. a) b) c) d) e) n.d.a. 2) Assinale a alternativa que contém uma descrição para a linguagem reconhecida pelo autômato A = ({q0, q1, q2, q3, q4}, {0,1}, ᵹ, q0, {q1}) onde: ᵹ(q0, 0) = {q2}, ᵹ(q0, 1) = {q0}, ᵹ(q0, ɛ) = {q1}, ᵹ(q1, 0) = {q2}, ᵹ(q1, 1) = {q1}, ᵹ(q2, 0) = {q3}, ᵹ(q2, 1) = {q2}, ᵹ(q3, 0) = {q4}, ᵹ(q3, 1) = {q3}, ᵹ(q4, 0) = {q1}, ᵹ(q4, 1) = {q4}. a) {w є {0,1}*| w contém um número de 0s que é múltiplo de 4} b) {w є {0,1}*| w contém um número par de 0s} c) {w є {0,1}*| w contém um número de 1s que é múltiplo de 4 e maior que 0} d) {w є {0,1}*| w contém um número de 0s que é par e maior que 0} e) n.d.a. 3) Assinale a alternativa que contém a descrição formal de um Autômato Finito Não determinístico que reconheça a linguagem {w | w contém um número ímpar de as e um número par de bs e não contém a subcadeia ab}. a) b) c) d) e) n.d.a. 4) Assinale a alternativa que contém uma descrição para a linguagem reconhecida pelo autômato B = ({q0, q1, q2, q3, q4, q5}, {a, b}, ᵹ, q0, {q2, q4}) onde: ᵹ(q0, ɛ) = {q1, q4}, ᵹ(q1, a) = {q2}, ᵹ(q1, b) = {q1}, ᵹ(q2, a) = {q3}, ᵹ(q2, b) = {q2}, ᵹ(q3, a) = {q2}, ᵹ(q3, b) = {q3}, ᵹ(q4, a) = {q4}, ᵹ(q4, b) = {q5}, ᵹ(q5, a) = {q5}, ᵹ(q5, b) = {q4}. a) { w є {a,b}* | w é formada por um número ímpar de as seguido por um número par de bs} b) { w є {a,b}* | w é formada por um número par de as seguido por um número ímpar de bs} c){ w є {a,b}* | w contém um número ímpar de as ou um número par de bs} d) { w є {a,b}* | w contém um número par de as ou um número ímpar de bs} e) n.d.a. 5) Considere as expressões regulares e descrições para linguagens geradas por elas e assinale a alternativa correta: I – a+(aUb)*b+ = { w є {a,b}* | w começa com a e termina com b} II – 1*(01+)* = { w є {0,1}* | todo 0 em w é seguido por pelo menos um 1} III – (00)* U (000)* = {w є {0}* | a quantidade de 0s é um múltiplo de 6} a)apenas I e II estão correta. b)apenas II está correta. c) todas estão corretas. d)apenas II e III estão corretas. e) n.d.a. 6) Assinale a alternativa que contém uma expressão regular para a linguagem L = {w | w tem um número igual de ocorrências de 10 e 01 como subcadeias} no alfabeto {0,1}. a)(0110 U 1001)* U 0 U 1 b)(01)*(10)* c)(0+(0*U1*)*0+) U (1+(0*U1*)*1+) U 0 U 1 U ɛ d)(0(0U1)*0)U(1(0U1)*1) e) n.d.a. 7) Assinale a alternativa correta em relação à transformação da expressão (0U1)*000(0U1)* em um AFN usando a construção de Thompson (vista em sala). a) Se invertermos os estados finais e não finais no AFN resultante obtemos um AFN que reconhece o complemento da expressão. b) o AFN resultante possui 20 estados. c) Cada operação estrela diminui em uma unidade o número de estados finais no autômato resultante. d) Cada operação de concatenação remove pelo menos um estado final do passo anterior da construção. e) n.d.a. 8)Assinale a alternativa que contém uma expressão regular que gere a mesma linguagem reconhecida pelo autômato A = ({q1, q2, q3}, {a, b}, ᵹ, q1, {q2, q3}) onde: ᵹ(q1, a) = q2, ᵹ(q1, b) = q3, ᵹ(q2, a) = q1, ᵹ(q2, b) = q2, ᵹ(q3, a) = q2, ᵹ(q3, b) = q1. a)((bb)*U(aa)*)b*U(ab*aU(bb)*)*b b) (bbU(aUba)b*a)*(bU(aUba)b*) c) a U b U ab*aUbbUab*a*Ub d) a U b U (ab*aUb(bUab*a))*b e) n.d.a. 9) Sejam A e B duas linguagens regulares e seja C uma linguagem não regular. Considere as afirmações a seguir. I – A ∩ B é uma linguagem regular. II – É possível usar o lema do bombeamento para provar que C não é regular. III – C certamente é uma linguagem não regular. IV – AB ∩ C certamente é uma linguagem regular. a) apenas II é correta. b) apenas I é correta. c) apenas I, III e IV são corretas. d) apenas I, II e IV são corretas. e) n.d.a. 10) Lema do bombeamento: Se A é uma linguagem regular, então, existe um número p tal que, se s é qualquer cadeia de A de comprimento no mínimo p, então s pode ser dividida em três partes, s= xyz, satisfazendo às seguintes condições: 1. para cada i ≥ 0, xyiz pertence a A. 2. |y| > 0 3. |xy| ≤ p Considere a linguagem L = {0i1j2k | i = j ou j = k e i, j, k > 0}. Assinale a alternativa contendo as escolhas que podemos fazer em relação aos parâmetros do lema do bombeamento de modo a provar que L não é regular. a) p = 3, s = 000111222, i = 0 b) s = 01p2p, x = 0, y = 1, z = 1p-12p, i = 2 c) s = 0p1p2p-1, i = 3 d) s = 01p2p, i = 3 e) n.d.a.
Compartilhar