Construa AFDs para reconhecer as seguintes linguagens:
\mathrm{w} \in{0,1} \mid w tem número par de 01 's e ímpar de 0 's }

Passo 1

O enunciado pede que a gente construa um autômato finito determinístico (AFD) sobre o alfabeto \{0,1\}\) que reconheça todas as palavras \(w\) tais que: \[w \in \{0,1\}^*\quad\text{satisfazendo}\quad \begin{cases} \text{o número de ocorrências do substring }01 \text{ em } w \text{ é par},\\[4pt] \text{o número de símbolos }0 \text{ em } w \text{ é ímpar}. \end{cases}
Informações dadas e objetivo:
\] - Alfabeto: \(\{0,1\}.
- Precisamos detectar duas propriedades simultâneas: (i) paridade do número de ocorrências de 01 (par/ímpar) e (ii) paridade do número de zeros (par/ímpar).
- Construir um AFD (determinístico) que aceite exatamente as palavras que têm 01 em quantidade par e zeros em quantidade ímpar.]

Passo 2

Ideia geral (explicação didática do que precisamos controlar):
  • Para saber se já vimos um 01 quando lemos um símbolo, precisamos saber se o símbolo anterior foi um 0. Ou seja, convém ter uma “bandeira” que diga se o último símbolo lido foi 0. Sem essa informação não dá para reconhecer quando aparece um novo 01.
  • Além disso, precisamos manter a paridade (par/ímpar) de duas contagens: (a) contagem de substrings 01 e (b) contagem de símbolos 0.
  • Cada uma dessas três informações é binária (dois valores cada): paridade de 01 ( \text{E} ou \text{O}), paridade de zeros ( \text{E} ou \text{O}), e flag “último foi 0?” ( \text{yes} ou \text{no}). Então precisamos de no máximo 2\cdot2\cdot2=8 estados para armazenar todas as combinações possíveis desses três bits de informação.
  • Vamos construir um AFD com 8 estados que representam essas combinações. A transição ao ler 0 ou 1 atualiza essas três informações de forma direta:
    • Ler 0: a paridade de zeros troca (par↔ímpar); a paridade de 01 não muda (um 01 só é gerado quando lemos 1 que segue um 0); a flag “último foi 0” passa a ser \text{yes}.
    • Ler 1: a paridade de zeros não muda; se a flag “último foi 0” era \text{yes} então acabamos de formar um 01 e a paridade de 01 troca (par↔ímpar); a flag “último foi 0” passa a ser \text{no}.

Passo 3

Definição dos estados e notação:
  • Cada estado será escrito como (p,z,r) onde
    • p \in \{\text{E},\text{O}\} indica a paridade do número de ocorrências de 01 vista até agora ( \text{E} = par, \text{O} = ímpar);
    • z \in \{\text{E},\text{O}\} indica a paridade do número de símbolos 0 vista até agora ( \text{E} = par, \text{O} = ímpar);
    • r \in \{\text{yes},\text{no}\} é a flag que vale \text{yes} se o último símbolo lido foi 0 (ou seja, estamos prontos para detectar um 01 se vier um 1), e \text{no} caso contrário.
  • Estado inicial: \bigl(\text{E},\text{E},\text{no}\bigr) (nenhum símbolo lido ainda: zero zeros, zero ocorrências de 01, e “último foi 0” = no).
  • Estados de aceitação: todos os estados com p=\text{E} (par de 01) e z=\text{O} (ímpar de zeros), isto é: \{ \, (\text{E},\text{O},\text{no}),\; (\text{E},\text{O},\text{yes}) \,\}.

Passo 4

Regras de transição (explicação e fórmula):
  • Seja o estado atual (p,z,r).
  • Ao ler um símbolo 0:
    • a paridade de zeros z troca de \text{E} para \text{O} ou de \text{O} para \text{E};
    • a paridade de 01 p permanece igual;
    • a flag r passa a ser \text{yes}.
      Em notação: leitura de 0 leva (p,z,r) em (p,\; z',\; \text{yes}) onde z' é o complemento de z.
  • Ao ler um símbolo 1:
    • a paridade de zeros z permanece igual;
    • se r=\text{yes} (ou seja, o último símbolo foi 0) então acabamos de ver um 01 e a paridade p troca; se r=\text{no} então p permanece;
    • a flag r passa a ser \text{no}.
      Em notação: leitura de 1 leva (p,z,r) em (p',\; z,\; \text{no}) onde p' é o complemento de p se r=\text{yes}, e p'=p se r=\text{no}.

Passo 5

Tabela completa de estados e transições (vamos rotular os 8 estados para facilitar):
  • Definimos as 8 etiquetas: \begin{array}{l} A = (\text{E},\text{E},\text{no}),\\\ B = (\text{E},\text{E},\text{yes}),\\\ C = (\text{E},\text{O},\text{no}),\\\ D = (\text{E},\text{O},\text{yes}),\\\ E = (\text{O},\text{E},\text{no}),\\\ F = (\text{O},\text{E},\text{yes}),\\\ G = (\text{O},\text{O},\text{no}),\\\ H = (\text{O},\text{O},\text{yes}). \end{array}
  • Estado inicial: A.
  • Estados de aceitação: C e D (pois ambos têm p=\text{E} e z=\text{O}).

    Agora a tabela de transições (cada linha: estado \xrightarrow{0} destino, \xrightarrow{1} destino):
  • A = (\text{E},\text{E},\text{no}): \;0\mapsto D,\;\; 1\mapsto A.
  • B = (\text{E},\text{E},\text{yes}): \;0\mapsto D,\;\; 1\mapsto E.
  • C = (\text{E},\text{O},\text{no}): \;0\mapsto B,\;\; 1\mapsto C.
  • D = (\text{E},\text{O},\text{yes}): \;0\mapsto B,\;\; 1\mapsto G.
  • E = (\text{O},\text{E},\text{no}): \;0\mapsto H,\;\; 1\mapsto E.
  • F = (\text{O},\text{E},\text{yes}): \;0\mapsto H,\;\; 1\mapsto A.
  • G = (\text{O},\text{O},\text{no}): \;0\mapsto F,\;\; 1\mapsto G.
  • H = (\text{O},\text{O},\text{yes}): \;0\mapsto F,\;\; 1\mapsto C.

    (As transições seguem exatamente as regras do passo anterior: leitura de 0 inverte a paridade de zeros e coloca a flag \text{yes}; leitura de 1 pode inverter a paridade de 01 se a flag era \text{yes}, e coloca a flag \text{no}.)

Passo 6

Exemplos de execução para ganhar confiança (como usar o AFD na prova):
  • Exemplo 1: palavra w=0.
    • Começamos em A. Ler 0 leva A\xrightarrow{0}D. Estado final D é de aceitação. De fato, w=0 tem um zero (ímpar) e zero ocorrências de 01 (par) ⇒ aceito.
  • Exemplo 2: palavra w=0101.
    • A\xrightarrow{0}D\xrightarrow{1}G\xrightarrow{0}F\xrightarrow{1}A. Estado final A não é de aceitação. Conferindo: 0101 tem duas ocorrências de 01 (par) e dois zeros (par) ⇒ não aceito, correto.
  • Exemplo 3: palavra w=001.
    • A\xrightarrow{0}D\xrightarrow{0}B\xrightarrow{1}E. Estado final E não é de aceitação. Conferindo: 001 tem um 01 (posições 2–3) → ímpar; zeros = 2 → par ⇒ não aceito, correto.

Passo 7

Observações finais e dicas para a prova:
  • Estratégia geral para exercícios assim: identifique todas as propriedades que precisam ser mantidas que sejam “locais” ou que possam ser expressas com paridades/flags; veja quantos bits de informação são necessários e construa estados que representem todas as combinações possíveis desses bits. Aqui foram 3 bits → 8 estados.
  • Ao desenhar, rotule os estados com as três informações (paridade de 01, paridade de zeros, flag “último foi 0”) — isso ajuda a evitar erros na tabela de transição.
  • Se precisar, mostre uma tabela de transição como a que dei; é a maneira mais clara de provar que o autômato está correto.

Resposta

Estados: \{A,B,C,D,E,F,G,H\} com
\begin{array}{l} A = (\text{E},\text{E},\text{no}),\\\ B = (\text{E},\text{E},\text{yes}),\\\ C = (\text{E},\text{O},\text{no}),\\\ D = (\text{E},\text{O},\text{yes}),\\\ E = (\text{O},\text{E},\text{no}),\\\ F = (\text{O},\text{E},\text{yes}),\\\ G = (\text{O},\text{O},\text{no}),\\\ H = (\text{O},\text{O},\text{yes}). \end{array}
Alfabeto: \{0,1\}. Estado inicial: A. Estados de aceitação: C,D.
Transições:
\begin{array}{l} A:\; 0\mapsto D,\; 1\mapsto A,\\[2pt] B:\; 0\mapsto D,\; 1\mapsto E,\\[2pt] C:\; 0\mapsto B,\; 1\mapsto C,\\[2pt] D:\; 0\mapsto B,\; 1\mapsto G,\\[2pt] E:\; 0\mapsto H,\; 1\mapsto E,\\[2pt] F:\; 0\mapsto H,\; 1\mapsto A,\\[2pt] G:\; 0\mapsto F,\; 1\mapsto G,\\[2pt] H:\; 0\mapsto F,\; 1\mapsto C. \end{array}]

Exercícios relacionados