Construa AFDs para reconhecer as seguintes linguagens:
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
Informações dadas e objetivo:
.
- Precisamos detectar duas propriedades simultâneas: (i) paridade do número de ocorrências de (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 em quantidade par e zeros em quantidade ímpar.]
.
- Precisamos detectar duas propriedades simultâneas: (i) paridade do número de ocorrências de
- Construir um AFD (determinístico) que aceite exatamente as palavras que têm
Passo 2
Ideia geral (explicação didática do que precisamos controlar):
- Para saber se já vimos um
quando lemos um símbolo, precisamos saber se o símbolo anterior foi um . Ou seja, convém ter uma “bandeira” que diga se o último símbolo lido foi . Sem essa informação não dá para reconhecer quando aparece um novo . - Além disso, precisamos manter a paridade (par/ímpar) de duas contagens: (a) contagem de substrings
e (b) contagem de símbolos . - Cada uma dessas três informações é binária (dois valores cada): paridade de
( ou ), paridade de zeros ( ou ), e flag “último foi 0?” ( ou ). Então precisamos de no máximo 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
ou atualiza essas três informações de forma direta: - Ler
: a paridade de zeros troca (par↔ímpar); a paridade de não muda (um só é gerado quando lemos que segue um ); a flag “último foi 0” passa a ser . - Ler
: a paridade de zeros não muda; se a flag “último foi 0” era então acabamos de formar um e a paridade de troca (par↔ímpar); a flag “último foi 0” passa a ser .
- Ler
Passo 3
Definição dos estados e notação:
- Cada estado será escrito como
onde -
indica a paridade do número de ocorrências de vista até agora ( = par, = ímpar); -
indica a paridade do número de símbolos vista até agora ( = par, = ímpar); -
é a flag que vale se o último símbolo lido foi (ou seja, estamos prontos para detectar um se vier um ), e caso contrário.
-
- Estado inicial:
(nenhum símbolo lido ainda: zero zeros, zero ocorrências de , e “último foi 0” = no). - Estados de aceitação: todos os estados com
(par de ) e (ímpar de zeros), isto é:
Passo 4
Regras de transição (explicação e fórmula):
- Seja o estado atual
. - Ao ler um símbolo
: - a paridade de zeros
troca de para ou de para ; - a paridade de
permanece igual; - a flag
passa a ser .
Em notação: leitura deleva em onde é o complemento de .
- a paridade de zeros
- Ao ler um símbolo
: - a paridade de zeros
permanece igual; - se
(ou seja, o último símbolo foi ) então acabamos de ver um e a paridade troca; se então permanece; - a flag
passa a ser .
Em notação: leitura deleva em onde é o complemento de se , e se .
- a paridade de zeros
Passo 5
Tabela completa de estados e transições (vamos rotular os 8 estados para facilitar):
- Definimos as 8 etiquetas:
- Estado inicial:
. - Estados de aceitação:
e (pois ambos têm e ).
Agora a tabela de transições (cada linha: estadodestino, destino):
-
: -
: -
: -
: -
: -
: -
: -
:
(As transições seguem exatamente as regras do passo anterior: leitura deinverte a paridade de zeros e coloca a flag ; leitura de pode inverter a paridade de se a flag era , e coloca a flag .)
Passo 6
Exemplos de execução para ganhar confiança (como usar o AFD na prova):
- Exemplo 1: palavra
. - Começamos em
. Ler leva . Estado final é de aceitação. De fato, tem um zero (ímpar) e zero ocorrências de (par) ⇒ aceito.
- Começamos em
- Exemplo 2: palavra
. -
. Estado final não é de aceitação. Conferindo: tem duas ocorrências de (par) e dois zeros (par) ⇒ não aceito, correto.
-
- Exemplo 3: palavra
. -
. Estado final não é de aceitação. Conferindo: tem um (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
, 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:
com
Alfabeto:
. Estado inicial:
. Estados de aceitação:
.
Transições:
Transições: