prova1-2020-2- t01-gabarito

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)
xb)
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}.
xa) {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) 
xb)
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}
xc){ 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}
xa)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)* 
xc)(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.
xd) 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
xb) (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.
xe) 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
xc) s = 0p1p2p-1, i = 3
d) s = 01p2p, i = 3
e) n.d.a.