Construa AFDs para reconhecer as seguintes linguagens:
\left\{w \in{0,1} \mid w=0^{n} 1^{n}\right\}

Passo 1

O enunciado pede que construamos AFDs para a linguagem
L=\{w\in\{0,1\}^* \mid w=0^{n}1^{n}\}.
Informações dadas e o que se pede:
  • O alfabeto é \{0,1\}.
  • A linguagem contém exatamente as cadeias formadas por alguns zeros seguidos por exatamente o mesmo número de uns; tipicamente n\ge 0. Assim a cadeia vazia \varepsilon pertence à linguagem (caso n=0).
  • 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 L. Aqui existe uma alternativa: provar que tal AFD não existe (isto é, L 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 L 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 \{0^n1^n\mid 0\le n\le k\}), porque às vezes em provas o professor aceita esse tipo de construção ou quer ver como se constrói um AFD quando n está limitado.

Passo 3

Lema de Bombeamento (afastando a ideia e explicando): o lema diz o seguinte.
Se uma linguagem R é regular, então existe um inteiro p\ge 1 (chamado comprimento de bombeamento) tal que toda palavra w\in R com |w|\ge p pode ser escrita como
w=xyz
satisfazendo:
  1. |xy|\le p,
  2. |y|\ge 1,
  3. para todo i\ge 0 vale xy^{i}z\in R.
Interpretação e intuição: para um autômato finito com p estados, ao ler uma palavra longa \ge p alguns estados são repetidos (pelo princípio da casa dos pombos). Essa repetição cria um trecho y 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 L.
  1. Suponha, para obter contradição, que L seja regular. Então existe p\ge 1 dado pelo lema.
  2. Considere a palavra específica
w = 0^{p}1^{p}.
Temos |w|=2p\ge p, então o lema se aplica: w=xyz com |xy|\le p e |y|\ge 1.
3. Como |xy|\le p, os símbolos da parte xy estão todos dentro dos primeiros p símbolos de w. Os primeiros p símbolos de w são todos zeros. Logo o bloco y consiste apenas de zeros; podemos escrever y=0^{m} com m\ge 1.
4. Pelo lema, para todo i\ge 0 a cadeia xy^{i}z deveria pertencer a L. Escolha i=0. Então a cadeia bombeada é
x z = 0^{p-m}1^{p}.
  1. A cadeia 0^{p-m}1^{p} não está em L porque o número de zeros (p-m) é menor que o número de uns p; em L eles precisam ser iguais. Assim obtemos uma contradição com a propriedade 3 do lema.
  2. Portanto a hipótese de que L é regular está errada. Conclusão: L 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 L=\{0^{n}1^{n}\} não é regular, não existe nenhum AFD que reconheça exatamente L.
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 n é limitado): apesar de não existir AFD para a linguagem inteira, para qualquer inteiro fixo k\ge 0 existe um AFD que reconhece a linguagem finita
L_{k}=\{0^{n}1^{n}\mid 0\le n\le k\}.
Vou descrever uma construção geral e dar um pequeno exemplo.
Construção geral para um dado k:
  • Estados:
    • q_{0},q_{1},\dots,q_{k}: estado q_{m} significa “li exatamente m zeros e ainda não comecei a ler uns”.
    • Para cada m\in\{1,\dots,k\} e para cada j\in\{1,\dots,m\} tenha um estado r_{m,j}: isto significa “li exatamente m zeros antes de trocar para a fase dos uns, e agora já li j uns (com 1\le j\le m)”.
    • Um estado de morte d (rejeição permanente) para leituras inválidas.
  • Estado inicial: q_{0} (zero zeros lidos).
  • Estados de aceitação: \{r_{m,m}\mid 0\le m\le k\}. (Para m=0 a condição de aceitar a cadeia vazia pode ser tratada marcando q_{0} como estado de aceitação ou usando r_{0,0}. Para uniformidade: trate q_{0} como já aceitando se quiser representar m=0.)
  • Transições:
    • Para m<k: \delta(q_{m},0)=q_{m+1}.
    • Para m=k: \delta(q_{k},0)=d (não aceitamos mais zeros além de k).
    • Para m\ge 1: \delta(q_{m},1)=r_{m,1}.
    • Para j<m: \delta(r_{m,j},1)=r_{m,j+1}.
    • Para qualquer r_{m,j}: \delta(r_{m,j},0)=d (não permitimos zeros depois de começar os uns).
    • Transições em d vão para d em ambos os símbolos.
    • Transições ilegais em q_{0} com símbolo 1 vão para d (porque 1 aparecendo antes de qualquer zero não produz cadeia da forma 0^{n}1^{n} com n\ge 0, exceto se aceitarmos n=0 e a cadeia for vazia).
  • Esse autômato reconhece exatamente todas as cadeias 0^{m}1^{m} com 0\le m\le k.
Contagem de estados (para ter noção do tamanho): número de estados = (k+1) estados q_{m} + \sum_{m=1}^{k} m = \frac{k(k+1)}{2} estados r_{m,j} + 1 estado d. Total
\frac{k(k+1)}{2} + (k+1) + 1 = \frac{k^{2}+3k+4}{2}.
Por exemplo, para k=2 (2^2+3\cdot2+4)/2=7 estados; dá para escrever explicitamente as transições nesse caso se precisar.

Passo 7

Resumo final e motivação curta:
  • A linguagem inteira \{0^{n}1^{n}\} 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 n. 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 n, 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 n limitado, use a construção do passo anterior.

Resposta

Não existe AFD que reconheça \{w\in\{0,1\}^*\mid w=0^{n}1^{n}\} (a linguagem não é regular).\nPara cada k\ge 0 existe AFD que reconhece \{0^{n}1^{n}\mid 0\le n\le k\}; uma construção geral foi dada no passo anterior.

Exercícios relacionados