degreeStuff
Aula Pratica 3
Autómatos e Liguagens de Programação | Data: 23/02/2021; Hora:16:00; Duração: 2h; Sala:CLAV_136;Docente: Francisco Coelho
Pagina Principal
Resolução de Exercicios
Exercício 3
Seja A=({0,1,2},{x,y},{(0,x,1),(0,y,0),(1,x,1),(1,y,2),(2,x,1),(2,y,0)},0,{0}) um AFD.
-
desenhe o diagrama de estados
a x y 0 1 0 1 1 2 2 1 0 - ✓ escreva uma expressão regular que represente a linguagem reconhecida por A
- ✓ repita a alínea anterior para o AFD A’ que apenas difere de A no conjunto dos estados de aceitação, que no caso de A é {0,1}
Exercício 5
Construa um autómato finito determinista que reconheça a linguagem da ER
| q’ | a | b |
|---|---|---|
| q’:fecho(a)={02} | 1 V ∅ | {3} U 3 |
| 1 | ∅ | {0,2} |
| 3 | 2 | ∅ |
| ∅ | ∅ | ∅ |
2 F |
∅ | 3 |
Exercício 8
Encontre um AFD que aceite a linguagem das palavras…
- com subpalavra 010 ou 101.
| q’ | 0 | 1 |
|---|---|---|
| q’=fecho(I) | I_1 | I_3 |
| I_3 | I_1 | I_32 |
| I_23 | I_14 | I_3 |
| I_14 | I_1 | I_23F |
| I_14F | I_1F | I_23F |
| I_23F | I_14F | I_3F |
| I_1F | I_1F | I_23F |
| I_3F | I_14F | I_3F |
