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 ( \Sigma={0,1}) que terminam em “10”. O conteúdo é construção de DFA para a linguagem \Sigma^*10. 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:
q_0: estado inicial, onde ainda não vimos um sufixo relevante.
q_1: lembramos que o último símbolo lido foi “1”.
q_2: 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 q_0:
  • Se lermos “0”, continuamos em q_0 (a palavra vista ainda não termina em “1”).
  • Se lermos “1”, vamos para q_1 (agora a palavra vista termina em “1”).

Passo 4

Transições a partir de q_1:
  • Se lermos “0”, a palavra termina em “10” ⇒ vamos para q_2.
  • Se lermos “1”, ela passa a terminar em “1” ⇒ mantemos em q_1.

Passo 5

Transições a partir de q_2: (já vimos “10” no fim)
  • Se lermos “0”, o novo sufixo final é “0” ⇒ não corresponde a “1” nem “10”, voltamos a q_0.
  • Se lermos “1”, o novo sufixo final é “1” ⇒ vamos para q_1.

Passo 6

Formalmente, o DFA é (Q,\Sigma,\delta,q_0,F) com
Q = \{q_0, q_1, q_2\},\quad \Sigma=\{0,1\},\quad q_0\text{ inicial},\quad F=\{q_2\},
e a função de transição dada pela tabela abaixo:
\begin{array}{c|cc} \delta & 0 & 1\\hline q_{0} & q_{0} & q_{1}\\\ q_{1} & q_{2} & q_{1}\\\ q_{2} & q_{0} & q_{1} \end{array}

Resposta

O autômato finito determinístico que reconhece \Sigma^*10 tem:
Q={ q_0,q_1,q_2},
inicial= q_0,
F={ q_2},
e transições
\delta(q,a)= \begin{cases} q_{0},&\text{se }q=q_{0}\text{ e }a=0,\\\ q_{1},&\text{se }q=q_{0}\text{ e }a=1,\\\ q_{2},&\text{se }q=q_{1}\text{ e }a=0,\\\ q_{1},&\text{se }q=q_{1}\text{ e }a=1,\\\ q_{0},&\text{se }q=q_{2}\text{ e }a=0,\\\ q_{1},&\text{se }q=q_{2}\text{ e }a=1. \end{cases}

Exercícios de Livros Relacionados