Construa um AFD , com alfabeto
, que aceitam as linguagens:
{Toda sub-cadeia 00 deve ser seguida imediatamente por um 1 }. obs. As cadeias 101, 0010, 0010011001 são aceitas. Mas as cadeias 0001, 00100 não deve ser aceitas.
{Toda sub-cadeia 00 deve ser seguida imediatamente por um 1 }. obs. As cadeias 101, 0010, 0010011001 são aceitas. Mas as cadeias 0001, 00100 não deve ser aceitas.
Passo 1
O que o enunciado pede: construir um AFD que aceite exatamente as cadeias sobre o alfabeto
que satisfazem a condição "toda sub-cadeia
, deve ser seguida imediatamente por um
". \n
Informações dadas e exemplos:
Informações dadas e exemplos:
- Alfabeto:
. - Deve aceitar cadeias como
, , . - Não deve aceitar cadeias como
(porque há um seguido por ) e (porque a cadeia termina em , sem o obrigatório após esse ).\n
Observação importante: cadeias que não contêm(por exemplo a cadeia vazia ou , ) também devem ser aceitas, já que não violam a condição.
Passo 2
Ideia principal (intuição): para decidir se uma cadeia é aceita precisamos, ao ler da esquerda para a direita, lembrar se acabamos de ver um
ou dois zeros consecutivos sem ter visto ainda o símbolo que deve obrigatoriamente vir depois. Em outras palavras precisamos de memória finita sobre o sufixo lido recentemente:
- Se o último símbolo lido não foi
(ou ainda não lemos nada), não há problema imediato. - Se acabamos de ver um único
, pode vir outro e aí teremos que exigir que o próximo símbolo seja . - Se acabamos de ver
, então o próximo símbolo tem de ser ; se for ou se a cadeia terminar nesse ponto, a cadeia deve ser rejeitada. - Se em algum momento vemos um padrão proibido (por exemplo um
depois de , ou a cadeia acaba quando estamos esperando um depois de ), então entramos num estado de erro (sink) que rejeita tudo a partir daí.
Portanto vamos criar estados que representam essas situações e transições que implementam essa exigência.
Passo 3
Definição formal do AFD. Vou apresentar o autômato como o quíntuplo
Escolhemos
Significado intuitivo dos estados:
-
: o sufixo lido não termina em (ou início); não há nenhuma exigência pendente. Estado de aceitação. -
: o sufixo lido termina em exatamente um (último símbolo é , mas não há um pendente). Estado de aceitação. -
: acabamos de ver e estamos obrigados a ver imediatamente um a seguir; se a cadeia terminar aqui ou vier , devemos rejeitar. Estado não aceitante. -
: estado de erro/sink (não aceitante) — já houve violação da condição.
Transição
(tabela):
Explicando a tabela:
- Em
: ao ler passamos para (agora terminamos em um único ); ao ler permanecemos em . - Em
: ao ler formamos e passamos para (precisamos que o próximo seja ); ao ler voltamos para . - Em
: ao ler satisfazemos a exigência após e voltamos para ; ao ler ou terminar aqui, a condição é violada, então vamos para (se vier ) ou não aceitamos caso a cadeia termine em . - Em
: loop em ambos símbolos — é um sink rejeitante.
Passo 4
Por que os estados de aceitação são
e
: uma cadeia é aceita se, ao terminar a leitura, não houver uma ocorrência de
que não tenha sido seguida por
. Se terminamos em
ou
isso significa que não estamos no meio de uma obrigação não satisfeita; mas se terminamos em
significa que a cadeia terminou logo após
(ou seja, não houve o
exigido) — então devemos rejeitar.
também é rejeitante por representar violação já detectada.
Testando com os exemplos (vou mostrar o percurso de estados, usando as cadeias entre aspas):
- Para
: . Termina em → aceita. - Para
: . Termina em → aceita. - Para
: (passando pelos blocos) sempre que ocorre o próximo símbolo é , então o automato passa por seguido de ; ao final chega em ou . Portanto aceita (pelo percurso concreto o automato nunca entra em nem termina em ). - Para
: . Termina em → rejeita, como desejado. - Para
: . Termina em → rejeita, como desejado.
Passo 5
Argumento de correção (por invariantes): Definimos os estados com significados precisos sobre o sufixo lido; a função de transição implementa exatamente a política "se você vê
então o próximo símbolo deve ser
". \n
- Invariante de posição: após processar qualquer prefixo
, o autômato fica em um estado que descreve corretamente a situação do sufixo relevante de : se o sufixo relevante não exige um (ou seja, não há um ainda sem confirmar), então estamos em ou ; se temos sem o seguinte, estamos em ; se já houve violação, estamos em . - Assim, uma cadeia é aceita sse ela termina em um estado que não exige um
(ou seja, em ou ). Então o autômato aceita exatamente as cadeias que satisfazem a condição pedida.
Se quiser, este autômato pode ser desenhado graficamente com os quatro estados e as setas conforme a tabela de transição. Ele é também minimal no sentido intuitivo: precisamos distinguir pelo menos as situações “nenhum zero pendente”, “um zero pendente”, “dois zeros esperando 1” e “violação”, portanto quatro estados são naturais aqui.