Turmas - 2º Semestre de 2025(Enade, 2005) Que cadeia é reconhecida pelo autômato representado pelo diagrama de estados a seguir?
M = ({0, 1}, {q0, q1, q2, q3}, δ, q0, {q1})
a. 101010
b. 111011000
c. 11111000
d. 10100
e. 00110011
Para se descobrir a solução da questão, é necessário executar o autômato apresentado com as entradas fornecidas.
Se, ao processar o último símbolo da entrada, o autômato estiver no estado final (q1), o autômato é encerrado e a entrada é aceita.
Se, ao processar o último símbolo da entrada, o autômato estiver num estado não final (q0, q2 ou q3), o autômato é encerrado e a entrada é rejeitada.
a. 101010
q0 - [1] 0 1 0 1 0
q1 - 1 [0] 1 0 1 0
q3 - 1 0 [1] 0 1 0
q2 - 1 0 1 [0] 1 0
q0 - 1 0 1 0 [1] 0
q1 - 1 0 1 0 1 [0]
q3 - 1 0 1 0 1 0 [ ] - REJEITA
b. 111011000
q0 - [1] 1 1 0 1 1 0 0 0
q1 - 1 [1] 1 0 1 1 0 0 0
q0 - 1 1 [1] 0 1 1 0 0 0
q1 - 1 1 1 [0] 1 1 0 0 0
q3 - 1 1 1 0 [1] 1 0 0 0
q2 - 1 1 1 0 1 [1] 0 0 0
q3 - 1 1 1 0 1 1 [0] 0 0
q1 - 1 1 1 0 1 1 0 [0] 0
q3 - 1 1 1 0 1 1 0 0 [0]
q1 - 1 1 1 0 1 1 0 0 0 [ ] - ACEITA
c. 11111000
q0 - [1] 1 1 1 1 0 0 0
q1 - 1 [1] 1 1 1 0 0 0
q0 - 1 1 [1] 1 1 0 0 0
q1 - 1 1 1 [1] 1 0 0 0
q0 - 1 1 1 1 [1] 0 0 0
q1 - 1 1 1 1 1 [0] 0 0
q3 - 1 1 1 1 1 0 [0] 0
q1 - 1 1 1 1 1 0 0 [0]
q3 - 1 1 1 1 1 0 0 0 [ ] - REJEITA
d. 10100
q0 - [1] 0 1 0 0
q1 - 1 [0] 1 0 0
q3 - 1 0 [1] 0 0
q2 - 1 0 1 [0] 0
q0 - 1 0 1 0 [0]
q2 - 1 0 1 0 0 [ ] - REJEITA
e. 00110011
q0 - [0] 0 1 1 0 0 1 1
q2 - 0 [0] 1 1 0 0 1 1
q0 - 0 0 [1] 1 0 0 1 1
q1 - 0 0 1 [1] 0 0 1 1
q0 - 0 0 1 1 [0] 0 1 1
q2 - 0 0 1 1 0 [0] 1 1
q0 - 0 0 1 1 0 0 [1] 1
q1 - 0 0 1 1 0 0 1 [1]
q0 - 0 0 1 1 0 0 1 1 [ ] - REJEITA
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 