Exercícios Linguagens Regulares

Prévia do material em texto

MINISTÉRIO DE EDUCAÇÃO
UNIVERSIDADE FEDERAL RURAL DO RIO DE JANEIRO
Instituto Multidisciplinar
Departamento de Ciência da Computação
Curso de Ciência da Computação
Linguagens Formais e Autômatos
Lista de Exercícios No. 02 
Linguagens Regulares
1) Considere as seguintes linguagens sobre o alfabeto {a, b}:
L2 = 
L3 = Σ*
2 a b
q0 q0 q0
3 a b
q0 q0 q0
a) Verifique se os autômatos M2 e M3 reconhecem as linguagens L2 e L3, 
respectivamente.
M2=({a, b}, {q0},2, q0, {})
M3=({a, b}, {q0}, 3, q0, {q0})
b) Existe alguma diferença entre as funções 2 e 3?
c) O que, exatamente, diferencia M2 de M3?
2) Transforme o NFA abaixo para um DFA.
3) Elabore um autômato que aceite a linguagem L = {w / w possui aaa como prefixo} 
sobre {a, b}.
4) Dadas as seguintes Gramáticas Regulares, encontre Autômatos Finitos equivalentes a 
elas e identifique as linguagens geradas pelas mesmas.
a) G = (V, T, P, S), onde:
V = {S, A, B, C} 
T = {a, b} 
P = { S → aA 
S → bC 
S → ε 
A → aS 
A → bB 
B → bC 
B → ε 
C → bB }
b) G = (V, T, P, S), onde: 
V={S, A, B, C, D} 
T={a, b} 
P={ S → aA 
A → bB 
B → bB 
B → aC 
C → aD 
C → ε 
D → bC }
5) Dados os seguintes Autômatos Finitos, encontre Gramáticas Regulares equivalentes a
eles e determine a linguagem reconhecida por eles:
a) 
b)
6) Desenvolva autômatos finitos determinísticos que reconheçam as seguintes 
linguagens sobre {a, b}(para o item c, considere que o alfabeto seja 
{0,1,2,3,4,5,6,7,8,9}):
a) {w / w possui aaa como subpalavra}
b) {w / o sufixo de w é aa}
c) {w / w possui um número ímpar de a e um número ímpar de b}
d) {w  Σ+ | a sequencia descrita por w corresponda a um valor inteiro par}
e) {ambn | m + n é par}
7) Desenvolva gramáticas regulares que gerem as seguintes linguagens sobre  = {a, b}:
a) {w / em w todo símbolo b é antecedido por um símbolo a}
b) {w / todo par de b consecutivos é precedido por um par de a consecutivos}
c) {w / w possui aba como prefixo}
8) Considere a linguagem L sobre o alfabeto {a, b}. Sabendo que L é regular, 
implemente um AFD que aceite L.
L = {w | w possui um número par de a e um número par de b}
9) Construa uma gramática que gere a linguagem (a+b)*(aa+bb).
10) Considerando as linguagens abaixo, dê a representação tabular e o diagrama de 
estados para cada uma delas. Em todos os casos o alfabeto é {0, 1}
a) {ω| ω começa com 1 e termina com 0}
b) {ω| toda posição ímpar de ω é 1}
11) Desenvolva um autômato finito determinístico que reconheça a seguinte linguagem 
sobre {a, b}:
L = {w / w possui um número par de “a” e ímpar de “b” ou w possui um número par de
“b” e ímpar de “a”}
12) Desenvolva AFN, com ou sem movimentos vazios, que reconheçam a seguinte 
linguagem:
{w / “aa” ou “bb” é subpalavra e “ccc” é sufixo de w}
13) Descreva em palavras as linguagens geradas pelas seguintes expressões regulares:
a) (aa+b)*(a+bb)
b) (b+ab)*(ɛ+a)
14) Apresente gramáticas e expressões regulares para as seguintes linguagens:
a) Linguagem em que as cadeias possuem no máximo quatro letras c's sobre Σ= {a, b, 
c}.
b) Linguagem em que as cadeias não possuem a's nem c's a direita de b's sobre Σ = {a, 
b, c}.
c) Linguagem em que as cadeias possuem pelo menos três símbolos iguais consecutivos
Σ = {a, b, c}.
15) Descreva as seguintes linguagens, sobre Σ = {0, 1}:
a) (0 +1)*1(0 +1)*
b) ((0 +1) (0 +1))*
c) 1*(01 + 1)*
d) (0 +1)*1
e) 0(0 +1)* + (0 +1)*1
16) Converta as expressões regulares a seguir em AF's:
a)(0 + 1)* 000 (0 + 1)*
b)(((00)*(11)) + 01)*
17) Aplique o algoritmo de tradução de formalismo de expressão regular para autômato 
finito:
a) (ab + ba)*(aa + bb)*
b) ab(abb* + baa*)*ba
18) Considere o autômato finito definido abaixo. Determine e justifique se as seguintes 
palavras na forma w=uvz satisfazem ao lema do bombeamento para as linguagens 
regulares:
a) u=ɛ, v=aab, z=aab
b) u=aa, v=baa, z=b
19) Para cada linguagem abaixo, desenvolva um correspondente autômato finito e 
exemplifique o lema do bombeamento para as linguagens regulares de forma a ilustrar a
existência de mais de um bombeamento:
a) {anbm | n0 e m0}
b) {anbmar | n0, m0 e r0}
20) Sobre o Lema do Bombeamento (pumping lemma) para linguagens regulares, 
considere as afirmativas a seguir:
I. Se o alfabeto Σ= {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que a linguagem L1 = { ω Σ*| ω termina com b} não é regular.
II. Se o alfabeto Σ= {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que a linguagem L1 = { (an)²| n ≥ 1}, não é regular. 
III. Se o alfabeto Σ= {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que as linguagens L3 = { an!| n ≥ 1}, L4 = { an bam ban+m| n, m ≥ 1} e L5 
= { am+1 bn+1| 2 ≤ n≤ m≤ 3n} não são regulares. 
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento. 
Assinale a alternativa correta. 
(a) Somente as afirmativas I e II são corretas. 
(b) Somente as afirmativas I e IV são corretas. 
(c) Somente as afirmativas III e IV são corretas. 
(d) Somente as afirmativas I, II e III são corretas. 
(e) Somente as afirmativas II, III e IV são corretas.
21) Prove que as seguintes linguagens não são regulares (supondo nN e mN):
a) {ww | w é palavra de {a, b}*}
b) {w | (w=anbm ou w=ambn), n m}
c) {0n1m | n ≤ m}
22) Minimize os autômatos finitos abaixo e determine seus estados equivalentes. Não se
esqueça de verificar os pré-requisitos do algoritmo de minimização, que são: 
 O autômato ser determinístico;
 O autômato não pode ter estados inúteis.
a)
b)
c)
d)
23) Verifique, através do algoritmo da tabela, se os seguintes autômatos são 
equivalentes.
24)(Exercício Complementar)Desenvolva um programa em computador (linguagem a 
sua escolha) que simule o processamento de qualquer autômato finito determinístico 
como segue:
 Entradas: Alfabeto, conjunto de estados, função de transição, estado inicial, 
conjunto de estados finais e as palavras a serem processadas.
 Saídas: Condição de parada ACEITA/REJEITA e identificação do estado de 
parada.
Dica: A parte central do algoritmo de simulação é realmente pequena, e pode ser 
expressa em poucas unidades de linha de código e consiste, basicamente, em um 
algoritmo que controla a mudança de estado do autômato a cada símbolo lido da 
entrada. Tal resultado comprova a simplicidade de se desenvolver um simulador 
genérico de autômato finito.
25) (ENADE 2005) Que cadeia é reconhecida pelo autômato representado pelo 
diagrama de estados ao lado?
(a) 101010
(b) 111011000
(c) 11111000
(d) 10100
(e) 00110011
26) (POSCOMP 2012) Seja um Autômato Finito Não Determinístico(AFN) com 6 
estados. Aplicando-se o algoritmo de conversão de um AFN para um Autômato Finito 
Determinístico (AFD), em quantos estados, no máximo, resultaria o AFD considerando-
se os estados inúteis?
(a) 12 
(b) 36 
(c) 64
(d) 1024
(e) 46656
27) (POSCOMP 2012) Assinale a alternativa que apresenta, corretamente, uma 
expressão regular que denota todas as strings de a’s e b’s que têm, pelo menos, dois b’s 
consecutivos.
(a) (a*+bb)(a+ba)*(a+b)* 
(b) (a+ba)*bb(ba+a)* 
(c) (a+b)*ba*b(a+b)*
(d) (a+bb)*(bb+a)*
(e) (a+ba)*bb(a+b)*
28)(POSCOMP 2012) Considere o autômato a seguir:
Assinale a alternativa que apresenta a expressão regular que gera a mesma linguagem 
reconhecida pelo autômato. 
(a) (ab)c*
(b) (a|b)c* 
(c) a(b|c)*
(d) a(bc)*
(e) a(b)*c
29) (POSCOMP 2013) Se o estado inicial for também estado final em um autômato 
finito, então esse autômato
(a) não aceita a cadeia vazia. 
(b) não tem outros estados finais. 
(c) é determinístico.
(d) aceita a cadeia vazia.
(e) é não determinístico.
30)(POSCOMP 2004) Seja Σ = {a,b} uma expressão regular denotando a linguagem L =
{w ϵ Σ* tal que toda ocorrência de “a” em w é imediatamenteseguida de “b”} é:
(a) (a*b)*
(b) (b + ab)*
(c) a*b
(d) b + (ab)*
(e) (ab)*
31)(POSCOMP 2008) Analise as seguintes igualdades de expressões regulares:
I. a* = (a*)*
II. (a+b)* = (b+a)*
III. a*+b* = (a+b)*
A análise permite concluir que
(a) somente as igualdades I e II são verdadeiras.
(b) somente a igualdade I é verdadeira.
(c) somente as igualdades II e III são verdadeiras.
(d) todas as igualdades são verdadeiras.
(e) nenhuma das igualdades é verdadeira.
32) (POSCOMP 2011) Considere a seguinte propriedade sobre uma linguagem formal 
L: “Existe um número p ≥ 0, tal que para qualquer palavra w  L, |w| ≥ p, existem 
palavras x, y e z, com y ≠ ε e |xy| ≤ p, tais que, para qualquer inteiro i ≥ 0, a palavra xyiz
L”.
Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F 
(falso) para as afirmativas a seguir.
( ) Se L é aceita por AFND, então L satisfaz a propriedade acima.
( ) A linguagem formada de 1’s e 0’s com igual quantidade de ocorrências das palavras
01 e 10 satisfaz a propriedade acima.
( ) A propriedade acima é falsa para a linguagem 0i1k2j / i, j, k ≥ 0 e se i = 1, então k = j.
( ) A linguagem {anbncn / n ≥ 0} não satisfaz a propriedade acima.
( ) A linguagem {anbm / n, m ≥ 0 e n ≠ m} satisfaz a propriedade acima.
Assinale a alternativa que contém, de cima para baixo, a sequência correta.
(a) V, V, V, V, F.
(b) V, V, F, V, F.
(c) V, F, V, F, F.
(d) F, V, V, F, V.
(e) F, V, F, V, V.