Pontifícia Universidade Católica de Minas Gerais (Unidade São Gabriel)
Programa de Pós-graduação – Mestrado em Informática
Disciplina: Fundamentos Teóricos da Computação
Professor : Zenilton Kleber Gonçalves do Patrocínio Júnior
Lista de Exercícios N.01
1. Construa AFDs para as seguintes linguagens:
a) { uavbxcy | u, v, x, y ∈ { a, b, c }* }.
b) { w ∈ { a, b }* | w começa com a e tem tamanho par }.
c) { w ∈ { a, b }* | w nunca tem mais de dois a’s consecutivos }.
d) { w ∈ { a, b }* | w tem número ímpar de ab’s }.
e) { w ∈ { a, b }* | | w | ≥ 2 e os a’s (se houver) precedem os b’s (se houver) }.
f) { w ∈ { a, b, c, d }* | os a’s (se houver) precedem os b’s (se houver) e os c’s (se houver)
precedem os d’s (se houver) }.
g) { xban | x ∈ { a, b }*, n ≥ 0 e x tem um número par de a’s }.
h) { xamban | x ∈ { a, b }*, m + n é par e x não termina em a }.
i) { w ∈ { a, b }* | toda subpalavra de w de tamanho 3 tem a’s e b’s }.
j) { w ∈ { a, b }* | w tem no máximo uma ocorrência de aa e no máximo uma ocorrência de
bb}.
2. Construa AFNs para as seguintes linguagens:
a) { w ∈ { 0, 1}* | | w | ≥ 4 e o segundo e o penúltimo símbolos são ambos 1 }.
b) { w ∈ { 0, 1}* | 00 não aparece nos 4 últimos símbolos de w }.
c) { w ∈ { 0, 1}* | entre dois 1’s de w há sempre um número par de 0’s, exceto nos 4 últimos
símbolos }.
d) { w ∈ { 0, 1}* | w tem uma subpalavra constituída de dois 1’s separados por um número par
de símbolos}.
e) { x03n | x ∈ { 0, 1}*, val(x) mod 3 = 1 e n ≥ 0 }, onde val(x) é o valor do número representado
por x na base 2.
3. Construa AFDs para as seguintes linguagens:
a) L1 = { w ∈ { 0, 1}* | | w | é divisível por 3 }.
b) L2 = { 0w0 | w ∈ { 0, 1}* }.
c) L3 = L1 ∪ L2.
d) L4 = L1 ∩ L2.
e) L5 = L1 ∩ L2.
4. Mostre que sim ou que não, justificando sua resposta:
a) Para qualquer linguagem L (inclusive aquelas que não são regulares), existem linguagens
regulares R1 e R2 tais que R1 ⊆ L ⊆ R2.
b) Todos os subconjuntos de uma linguagem regular são também linguagens regulares.
c) Há linguagens regulares que têm como subconjuntos linguagens que não são regulares.
d) A união de duas linguagens que não são regulares pode ser ou não uma linguagem regular.
e) A interseção de duas linguagens que não são regulares pode ser ou não uma linguagem
regular.
f) O complemento de uma linguagem que não é regular pode ser ou não uma linguagem
regular.
5. Prove que os seguintes conjuntos não são linguagens regulares:
a) { 0n 1n+10 | n ≥ 0 }.
b) { 0n y | y ∈ { 0, 1 }* e | y | ≤ n }.
c) { 0m 1n | m ≠ n }.
d) { am bn cm+n | m, n > 0 }.
2
e) { an bn | n ≥ 0 }.
3
f) { an | n ≥ 0 }.
g) { am bn | n ≤ m ≤ 2n }.
h) { xx | x ∈ { a, b }* }.
i) { uū | u ∈ { 0, 1 }* }, onde ū é obtido de u substituindo-se 0 por 1 e 1 por 0.
Exemplo: 011 = 100.
j) { w ∈ { 0, 1 }* | w ≠ wR }.
k) { w ∈ { a, b, c }* | o número de a’s, b’s e c’s, em w, é o mesmo }.
l) { w ∈ { 0, 1 }* | o número de 0’s em w é um cubo perfeito }.
m) { 0m 1n | mdc(m, n) = 1 }.
n) { ak bm cn | k ≠ m ou m ≠ n }.
o) { 0m 1n 0n | m, n > 0 }.
6. Sejam L1 e L2 duas linguagens. Mostre que sim ou que não:
a) se L1 ∪ L2 é uma linguagem regular então L1 é uma linguagem regular.
b) se L1L2 é uma linguagem regular então L1 é uma linguagem regular.
c) se L1* é uma linguagem regular então L1 é uma linguagem regular.
d) se L1 é uma linguagem regular então { w | w é uma subpalavra de L1} é uma linguagem
regular.
7. Mostre que a classe das linguagens regulares é fechada sob as seguintes operações:
a) pref (L) = { x | xy ∈ L } (os prefixos das palavras de L).
b) suf (L) = { y | xy ∈ L } (os sufixos das palavras de L).
c) rev (L) = { wR | w ∈ L } (os reversos das palavras de L).
d) crev (L) = { xyR | x, y ∈ L } (a concatenação das palavras de L com os reversos das palavras
de L).
8. Determine expressões regulares e gramáticas regulares para as seguintes linguagens sob { 0, 1 }*:
a) Conjunto das palavras em que 0’s só podem ocorrer nas posições pares.
b) Conjunto das palavras que não contêm 000.
c) Conjunto das palavras em que cada subpalavra de tamanho 4 contém pelo menos três 1’s.
d) Conjunto das palavras que não contêm 00 nos últimos 4 símbolos.
e) Conjunto das palavras que não contêm 00, a não ser nos últimos 4 símbolos (se tiver).
9. Determine uma expressão regular e uma gramática regular para o AFD cujo diagrama é
representado pela figura abaixo:
10. Considere as seguintes ERs :
•
•
•
•
r1 = (a ∪ b)*(ab ∪ ba)(a ∪ b)*
r2 = ab*
r3 = a(b*ab*a)*
r4 = (aa ∪ bb ∪ (ab ∪ ba)(aa ∪ bb)*(ab ∪ ba))*
Encontre ERs para:
a) L(r1);
b) L(r2);
c) L(r3);
d) L(r4);
e) L(r1) ∩ L(r4);
f) L(r1) − L(r4).
11. Construa uma máquina de Moore que:
a) Determine o resto da divisão por 5 de um número na representação binária.
b) Determine a quantidade de 1’s presente nos últimos 3 dígitos de uma palavra sobre o alfabeto
{ 0, 1 }.
12. Construa uma máquina de Mealy que:
a) Determine o quociente da divisão por 5 de um número na representação binária.
b) Some dois números na base binária, em que os números são representados através do
alfabeto { [0,0], [0,1], [1,0], [1,1] } com os dígitos menos significativos em primeiro lugar,
sendo que os dígitos mais significativos (pelo menos um) sempre serão zeros. Por exemplo,
para somar 13 e 20, deve-se fornecer a palavra ([0,0][0,1][1,0][1,1][0,0][1,0])R, em que os
primeiros dígitos (001101)R codificam o número 13 e os segundos (010100)R codificam o
número 20; e a saída deve ser (100001)R, que codifica o número 33.
13. Construa uma máquina de Mealy equivalente a máquina de Moore do exercício 11(b).
14. Construa uma máquina de Moore equivalente a máquina de Mealy do exercício 12(a).