Turmas - 2º Semestre de 2025O método da construção de subconjuntos é um procedimento sistemático que converte um autômato finito com movimentos vazios num autômato finito determinístico. O princípio associado a esse método é criar novos estados, no autômato finito determinístico, que estejam associados a todas as possibilidades de estados originais em um dado momento da análise da sentença no processo de reconhecimento. Para cada estado original, essas possibilidades incluem o estado do autômato finito com movimentos vazios e todos os estados que podem ser atingidos a partir dele com transições pela string vazia. Converta, usando o método da construção de subconjuntos, o autômato finito não-determinístico com movimentos vazios apresentado a seguir para um autômato finito determinístico.
M = ({a, b, c}, {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14, q15, q16, q17, q18, q19}, δ, q0, {q19})
Para se descobrir a solução da questão, é necessário realizar o método da construção de subconjuntos sobre o autômato finito com movimentos vazios apresentado.
ε*{q0} → (s0)
ε*{q2} → (s1)
ε*{q7, q16} → (s2)
ε*{q9} → (s3)
Autômato Finito Determinístico resultante da aplicação do método da construção de subconjuntos sobre o autômato finito não-determinístico com movimentos vazios apresentado.
M = ({a, b, c}, {s0, s1, s2, s3}, δ, s0, {s1, s2, s3})
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 