Construa um AFD , com alfabeto
, que aceitam as linguagens:
{Toda sub-cadeia de tamanho 4 deve ter no máximo dois " 0 "
. obs. As cadeias 001110, 011001 são aceitas. Mas as cadeias 10010 não é aceita.
{Toda sub-cadeia de tamanho 4 deve ter no máximo dois " 0 "
Passo 1
O enunciado pede: construir um autômato finito determinístico (AFD) com alfabeto
que aceite exatamente as cadeias em que "toda sub-cadeia de tamanho 4 deve ter no máximo dois
". Informações dadas/observações do enunciado:
- Exemplos aceitos:
e . - Exemplo rejeitado:
. - Interpretação precisa: para cada posição da palavra onde existe uma subcadeia de comprimento
, essa subcadeia não pode conter ou zeros (ou seja, deve ter no máximo dois zeros). - Para palavras com comprimento menor que
a condição vale trivialmente (são aceitas).
Passo 2
Idea central (sem resolver ainda): para verificar a condição "toda sub-cadeia de tamanho
tem no máximo dois
", quando eu leio o próximo símbolo eu preciso saber quais foram os últimos
símbolos lidos, porque ao concatenar o símbolo atual com os últimos
eu obtenho a sub-cadeia de tamanho
que precisa ser checada. Então o autômato deve “lembrar” o sufixo (sufixo = final) da palavra lida de tamanho até
. Se ao formar uma janela de
símbolos essa janela tiver
ou mais zeros, vamos para um estado isolado de rejeição (estado morte) e ficamos nele para sempre. Por isso construiremos estados que representam todos os sufixos possíveis de comprimento
e um estado morte.
Explicação curta de por que isso basta:
- Se eu sempre guardo os últimos
símbolos, quando chega um novo símbolo eu consigo formar a janela de (últimos + novo) e checar o número de zeros nela. Isso é exatamente o que um DFA precisa: memória finita (aqui os últimos símbolos) para decidir cada próxima transição.
Passo 3
Definição dos estados (intuição): cada estado corresponde ao sufixo lido mais recente de tamanho até
. Vou nomear os estados exatamente pelo sufixo que representam. Os estados são:
Aqui
é o sufixo vazio;
é o estado que representa que já foi encontrada alguma janela de tamanho
com
ou
zeros (violação).
Passo 4
Estado inicial e estados de aceitação:
- Estado inicial
. - Estados de aceitação
: todas as cadeias que não caíram em violação são aceitas, portanto
O estado
não é de aceitação. Observação: palavras de comprimento menor que
ficam em algum estado que não é
, então são aceitas, como queremos.
Passo 5
Regra geral de transição (descrição do
):
- Se o autômato está em um estado que representa um sufixo
com e lê o símbolo , então o novo sufixo é simplesmente concatenado com ; o estado passa a ser o sufixo final de símbolos:
(Ex.: de
com
vai para o estado
se
; de
com
vai para
.)
- Se o autômato está em um estado que representa um sufixo
com e lê , então formamos a janela de tamanho . Se essa janela contém zeros (ou seja, exatamente 3 ou 4 zeros), houve violação e
Caso contrário (a janela tem 0, 1 ou 2 zeros), então o novo sufixo de tamanho
é os últimos
símbolos de
, então
- Para o estado morte
, qualquer símbolo leva de volta a :
Passo 6
Vou dar alguns exemplos concretos de transições para fixar a ideia (usando a regra acima):
- Estado
e : . Conte os zeros em : há três zeros, então . - Estado
e : . Conta zeros: duas zeros apenas, então (últimos 3 símbolos de são ). - Estado
(tamanho 2) e : . Como , não existe janela de 4 ainda; . - Estado
e : .
Passo 7
Traço o processamento dos exemplos do enunciado para mostrar que o autômato aceitaria/rejeitaria como pedido (aplico as regras acima passo a passo):
-
:
- Começa em
. - Lê
: vai para . - Lê
: vai para . - Lê
: vai para . - Lê
: agora com e . tem dois zeros → . - Lê
: com e . tem um zero → . - Lê
: com e . tem um zero → .
Termina em, que é um estado de aceitação → palavra aceita.
-
:
-
(pois tem dois zeros?) — verificar: tem dois zeros? Na verdade tem dois zeros (os extremos). Logo . - Continua
(pois não foi formado ainda? atenção: de ao ler formamos que tem três zeros? contar zeros em : dois zeros → \delta(110,0)=100)). - Continua
(pois tem dois zeros → últimos 3 símbolos são ).
Termina em(aceitação). Portanto aceita.
-
:
-
(pois tem dois zeros) agora e : tem três zeros → vai para .
Termina em(rejeição). Portanto rejeitado, como desejado.
Passo 8
Observações finais: o autômato descrito é determinístico, aceita exatamente as cadeias em que nenhuma janela de tamanho
tem
ou
zeros. A construção é mecânica e direta: reter os últimos
símbolos basta para checar a condição ao ler o próximo símbolo. O único estado não aceitante é o estado morte
.
Resposta
e
definida por: