Construa um autômato finito determinístico que reconheça o conjunto de todas as seqüências de bits que terminam com 10.
Passo 1
O enunciado pede um autômato finito determinístico (DFA) que reconheça todas as sequências de bits (
{0,1}) que terminam em “10”. O conteúdo é construção de DFA para a linguagem
. Para resolver, precisamos de estados que lembrem os últimos símbolos lidos (no máximo 2), de modo a aceitar exatamente quando a cadeia terminar em “10”.
Passo 2
Vamos criar três estados:
• : estado inicial, onde ainda não vimos um sufixo relevante.
• : lembramos que o último símbolo lido foi “1”.
• : aceitamos, pois os dois últimos símbolos lidos formam “10”.
•
•
•
A ideia é que, ao ler cada bit, atualizamos qual sufixo (de até comprimento 2) a palavra lida termina.
Passo 3
Transições a partir de
:
- Se lermos “0”, continuamos em
(a palavra vista ainda não termina em “1”). - Se lermos “1”, vamos para
(agora a palavra vista termina em “1”).
Passo 4
Transições a partir de
:
- Se lermos “0”, a palavra termina em “10” ⇒ vamos para
. - Se lermos “1”, ela passa a terminar em “1” ⇒ mantemos em
.
Passo 5
Transições a partir de
: (já vimos “10” no fim)
- Se lermos “0”, o novo sufixo final é “0” ⇒ não corresponde a “1” nem “10”, voltamos a
. - Se lermos “1”, o novo sufixo final é “1” ⇒ vamos para
.
Passo 6
Formalmente, o DFA é
com
e a função de transição dada pela tabela abaixo:
Resposta
O autômato finito determinístico que reconhece
tem:
Q={ },
inicial= ,
F={ },
e transições
Q={
inicial=
F={
e transições