Construa AFDs para reconhecer as seguintes linguagens:
Passo 1
O enunciado pede que construamos AFDs para a linguagem
Informações dadas e o que se pede:
- O alfabeto é
. - A linguagem contém exatamente as cadeias formadas por alguns zeros seguidos por exatamente o mesmo número de uns; tipicamente
. Assim a cadeia vazia pertence à linguagem (caso ). - O pedido literal é “construir AFDs” que reconheçam essa linguagem.
Passo 2
Decisão de método (explicando por que): antes de tentar desenhar um autômato, precisamos verificar se existe algum AFD (determinístico e finito) que reconheça
. Aqui existe uma alternativa: provar que tal AFD não existe (isto é,
não é regular). Vou usar o Lema de Bombeamento (pumping lemma) para linguagens regulares — é uma ferramenta padrão e relativamente simples para mostrar que certas linguagens (como esta) não são regulares. Se descobrirmos que
não é regular, concluímos que não existe AFD que a reconheça. Como complemento prático, vou também construir AFDs que reconhecem aproximações finitas da linguagem (casos
), porque às vezes em provas o professor aceita esse tipo de construção ou quer ver como se constrói um AFD quando
está limitado.
Passo 3
Lema de Bombeamento (afastando a ideia e explicando): o lema diz o seguinte.
Se uma linguagem
é regular, então existe um inteiro
(chamado comprimento de bombeamento) tal que toda palavra
com
pode ser escrita como
satisfazendo:
-
, -
, - para todo
vale .
Interpretação e intuição: para um autômato finito com
estados, ao ler uma palavra longa
alguns estados são repetidos (pelo princípio da casa dos pombos). Essa repetição cria um trecho
que pode ser “bombeado” (repetido qualquer número de vezes, inclusive zero) sem sair da linguagem, se a linguagem fosse regular. Assim, para provar que uma linguagem não é regular, assumimos que ela é e usamos o lema para obter uma contradição.
Passo 4
Aplicando o Lema de Bombeamento a
.
- Suponha, para obter contradição, que
seja regular. Então existe dado pelo lema. - Considere a palavra específica
Temos
, então o lema se aplica:
com
e
.
3. Como , os símbolos da parte
estão todos dentro dos primeiros
símbolos de
. Os primeiros
símbolos de
são todos zeros. Logo o bloco
consiste apenas de zeros; podemos escrever
com
.
4. Pelo lema, para todo a cadeia
deveria pertencer a
. Escolha
. Então a cadeia bombeada é
3. Como
4. Pelo lema, para todo
- A cadeia
não está em porque o número de zeros é menor que o número de uns ; em eles precisam ser iguais. Assim obtemos uma contradição com a propriedade 3 do lema. - Portanto a hipótese de que
é regular está errada. Conclusão: não é regular.
Passo 5
Consequência imediata para AFDs:
- Um AFD (autômato finito determinístico) tem um número finito de estados e só pode reconhecer linguagens regulares.
- Como
não é regular, não existe nenhum AFD que reconheça exatamente .
Não desanime: essa é uma das linguagens clássicas que exemplificam limites dos autômatos finitos — é normal ficar surpreso na primeira vez.
Passo 6
Construções úteis e práticas (quando
é limitado): apesar de não existir AFD para a linguagem inteira, para qualquer inteiro fixo
existe um AFD que reconhece a linguagem finita
Vou descrever uma construção geral e dar um pequeno exemplo.
Construção geral para um dado
:
- Estados:
-
: estado significa “li exatamente zeros e ainda não comecei a ler uns”. - Para cada
e para cada tenha um estado : isto significa “li exatamente zeros antes de trocar para a fase dos uns, e agora já li uns (com )”. - Um estado de morte
(rejeição permanente) para leituras inválidas.
-
- Estado inicial:
(zero zeros lidos). - Estados de aceitação:
. (Para a condição de aceitar a cadeia vazia pode ser tratada marcando como estado de aceitação ou usando . Para uniformidade: trate como já aceitando se quiser representar .) - Transições:
- Para
: . - Para
: (não aceitamos mais zeros além de ). - Para
: . - Para
: . - Para qualquer
: (não permitimos zeros depois de começar os uns). - Transições em
vão para em ambos os símbolos. - Transições ilegais em
com símbolo vão para (porque aparecendo antes de qualquer zero não produz cadeia da forma com , exceto se aceitarmos e a cadeia for vazia).
- Para
- Esse autômato reconhece exatamente todas as cadeias
com .
Contagem de estados (para ter noção do tamanho): número de estados =
estados
+
estados
+
estado
. Total
Por exemplo, para
há
estados; dá para escrever explicitamente as transições nesse caso se precisar.
Passo 7
Resumo final e motivação curta:
- A linguagem inteira
exige que o autômato “lembre” quantos zeros viu para comparar com os uns. Um AFD tem memória finita (um número fixo de estados) e não consegue lembrar um número arbitrariamente grande . O Lema de Bombeamento formaliza essa limitação e mostra a contradição. - Se a sua prova pedir um AFD para a linguagem sem restrição em
, a resposta correta é afirmar que isso é impossível e apresentar a prova (por exemplo, pelo Lema de Bombeamento). Se a prova pedir AFDs para casos com limitado, use a construção do passo anterior.
Resposta
Não existe AFD que reconheça
(a linguagem não é regular).\nPara cada
existe AFD que reconhece
; uma construção geral foi dada no passo anterior.