Estudos do livro de Sipser #01: Autômatos Finitos Determinísticos (DFA)

Intplex — Fri, 19 Jun 2026 19:02:00 +0000

Este é o primeiro post que faço na plataforma e também o início da série dos meus estudos de Teoria da Computação. Logo como é o primeiro post, vou fazer os primeiros dois exercícios do capítulo um de expressões regulares.

1.1.
Neste exercício se pede o seguinte: A seguir estão os diagramas de estado de dois AFDs, M1 e M2. Responda às seguintes questôes sobre cada uma dessas máquinas.

M2:

M1:

As perguntas são para cada autômato:
a. Qual o estado inicial?
b. Qual os conjuntos dos estados de aceitação?
c. Por qual sequência de estados a máquina passa para a entrada aabb?
d. A máquina aceita a cadeia aabb?
e. A máquina aceita a cadeia vazia?

Para M1:
a. O estado inicial é q0.
b. {q2}
c. Para a entrada aabb: q0 -a-> q2, q2 -a-> q1, q1 -b-> q0, q0 -b> q0 ou q0, q2, q1, q0, q0.
d. Não aceita.
e. Não aceita.

Para M2:
a. O estado inicial é q4.
b. {q4, q7}
c. Para a entrada aabb: q4 -a-> q4, q4 -a-> q4, q4 -b-> q6, q6 -b-> q7 ou q4, q4, q4, q6, q7.
d. Aceita.
e. Aceita, pois o estado q4 é estado inicial e de aceitação simultaneamente.

1.2.
A questão pede: Dê a descrição formal das máquinas M1 e M2 desenhadas no exercício 1.1.

M1 = ({q0, q1, q2}, {a, b}, função de transição, q0, {q2})
função de transição:
|------| a | b |
|------|----|----|
| q0 | q2 | q0 |
| q1 | q2 | q0 |
| q2 | q1 | q1 |
M2 = ({q4, q5, q6, q7}, {a, b}, função de transição, q4, {q4, q7})
função de transição:
|------| a | b |
|------|----|----|
| q4 | q4 | q6 |
| q5 | q6 | q4 |
| q6 | q5 | q7 |
| q7 | q5 | q7 |

DEV Community: Intplex

Estudos do livro de Sipser #01: Autômatos Finitos Determinísticos (DFA)