Lista de Exercícios de Teoria da Computação

UERJ Universidade do Estado do Rio de Janeiro
IME Instituto de Matemática e Estatística
DICC Departamento de Informática e Ciência da Computação
Profa. Maria Alice Silveira de Brito

IME4614 Compiladores I T01 Exercícios da primeira parte da matéria
P→02468
1. Considere as seguintes linguagens regulares definidas a seguir sobre o alfabeto Σ = {0,1} e para cada uma delas:
i) Enumere os seus primeiros elementos – linguagens dos itens K a V. ii) Apresente uma gramática regular que a gere. iii) Apresente um autômato finito determinístico que a reconheça. iv) Apresente uma expressão regular que a denote.
*) Σ* = { ε, 0, 1,
00,01,10,11,000,001,010,011,100,101,110,111,...}
(especial)
1. LA = { ε}

2.

LB = { 0 }

3. LC = { 1 }

4.

LD = { 00 }

5. LE = { 11 }

6.

LF = { 000 }

7. LG = { 00, 0000, 000000, ... }

8. LH = { ε, 00, 0000,
000000, ... }

9. LI = { 111, 111111, 111111111,
...}

10. LJ = { ε, 111,
111111, 111111111, ...}

11. LK = { w ∈ Σ*  w possui um número de símbolos múltiplo de
2 e |w| ≥ 0 }

12. LL = { w ∈ Σ*  w possui um número de símbolos múltiplo de 2 e
|w| ≥ 2 }

13. LM = { w ∈ Σ*  w possui um número de símbolos múltiplo de
3}

14. LN = { w ∈ Σ*  w possui um número de símbolos múltiplo de 2 e começa com 00 }

15. LO = { w ∈ Σ* w possui um número de símbolos múltiplo de
3 e termina com 11 }

16. LP = { w ∈ Σ* w possui um número de símbolos múltiplo de 3 e começa com 000 }

17. LQ = { w ∈ Σ* w não possui nem 0’s nem 1’s isolados }

18. LR = { w ∈ Σ*
símbolos inicial e final de w são distintos }

19. LS = { w ∈ Σ* w começa com um número par de 0’s e termina com um número ímpar de 1’s }

20. LT = { w ∈ Σ* w possui exatamente três
1’s}

21. LU = { w ∈ Σ* w possui exatamente três 1’s não consecutivos} 22. LV = { w ∈ Σ* w é constituída de um ou mais blocos consecutivos, cada um com cinco símbolos, tendo pelo menos dois
0´s}

2.

Essa