Prove que as seguintes linguagens a seguir não são regulares e construa um Autômato de pilha com aceitação por estado final para cada uma delas.
\left\{a^{i} b^{j} c^{k}: i \neq j\right. ou i \neq k ou \left.j \neq k\right\}

Passo 1

O enunciado pede para a linguagem
L = \{\,a^i b^j c^k \mid i\neq j\;\lor\;i\neq k\;\lor\;j\neq k\}
sobre o alfabeto \{a,b,c\}. Primeiro vamos provar que L não é regular. Em seguida, para cada uma das três condições
  1. i\neq j,
  2. i\neq k,
  3. j\neq k,
    vamos construir um autômato de pilha (PDA) que reconheça exatamente \{a^i b^j c^k:tal que a condição correspondente valha \}, com aceitação por estado final.

Passo 2

Prova de que L não é regular por fechamento de linguagens regulares:
  1. É sabido que R = a^* b^* c^* é regular.
  2. Note que o complemento de L dentro de R é R \setminus L = \{\,a^i b^j c^k \mid \neg(i\neq j\lor i\neq k\lor j\neq k)\} = \{\,a^n b^n c^n \mid n\ge0\},e essa última linguagem não é regular (pode‐se provar por pumping lemma).
  3. As linguagens regulares são fechadas sob diferença com outra regular. Se L fosse regular, então R\setminus L seria regular, contradizendo o fato de \{a^n b^n c^n\} não ser regular.
    Logo, L não é regular.

Passo 3

PDA para L_1 = \{a^i b^j c^k \mid i\neq j\}.
Intuição: empilhar um X para cada a, depois desempilhar um X para cada b.
  • Se ao ler um b não houver X para desempilhar, então j>i: vamos para um estado final e só consumimos o resto de b e de c.
  • Se, ao terminar de ler todos os b (isto é, chegar ao primeiro c ou ao fim), ainda restar X na pilha, então i>j: mudamos para outro estado final e consumimos o resto de c.
    Descrição dos estados e transições (pilha inicia com \bot no fundo):
    Estados: q_0 (inicial), q_1, q_{f1}, q_{f2}.
    Alfabeto de pilha: \{X,\bot\}.
Transições \delta:
  1. Em q_0, ao ler a e ver topo \bot ou X, empilha X:
    \delta(q_0,a,\bot)\ni (q_0, X\bot),
    \delta(q_0,a,X)\ni (q_0, XX).
  2. Em q_0, ao ler o primeiro b, vai para q_1 sem mexer na pilha.
  3. Em q_1:
    • Ao ler b e ver topo X, desempilha:
      \delta(q_1,b,X)\ni (q_1,\varepsilon).
    • Ao ler b e ver topo \bot, não há X para desempilhar ⇒ j>i. Transita para q_{f1} (final) e mantém \bot.
    • Ao ler c em q_1:
      • Se topo é X, desempilha tudo remanescente de X em transição-ε para q_{f2} (final).
      • Se topo é \bot, chegamos a i=j; mas nesse caso não há transição para estado final, então a cadeia é rejeitada.
  4. Em q_{f1} e q_{f2}, para qualquer b ou c, permanece no próprio estado consumindo o símbolo e sem tocar a pilha.
Os dois estados q_{f1},q_{f2} são finais e garantem que aceitamos exatamente quando i\neq j.

Passo 4

PDA para L_2 = \{a^i b^j c^k \mid i\neq k\}.
Intuição: empilhar X em cada a, ignorar b, depois desempilhar em cada c.
  • Se na fase de c vier um c com topo \bot, então k>i: vamos para estado final e consumimos o resto de c.
  • Se ao terminar a entrada ainda restar X na pilha, então i>k: mudamos para um estado final.
Estados: p_0 (inicial), p_1, p_{f1}, p_{f2}.
Transições principais:
  1. Em p_0, ao ler a, empilha X.
  2. Em p_0, ao ler b, permanece em p_0 sem mexer na pilha.
  3. Em p_0, ao ler o primeiro c, vai para p_1.
  4. Em p_1:
    • Ao ler c com topo X, desempilha um X.
    • Ao ler c com topo \bot, transita para p_{f1} (final) e consome o resto de c.
    • Em ε-transição de p_1 para p_{f2} se ao final da entrada ainda restar X na pilha (passo-ε que esvazia toda pilha de X e entra em p_{f2}).
  5. Em p_{f1},p_{f2}, para qualquer c, permanece no próprio estado consumindo input.
Os estados finais p_{f1},p_{f2} capturam exatamente as duas possibilidades i<k ou i>k.

Passo 5

PDA para L_3 = \{a^i b^j c^k \mid j\neq k\}.
Intuição: ignorar a, empilhar X em cada b, depois desempilhar em cada c.
  • Se ao ler um c não houver X na pilha, então k>j: vamos a um estado final.
  • Se ao final da entrada restar X, então j>k: indo a outro estado final.
Estados: r_0 (inicial), r_1, r_{f1}, r_{f2}.
Transições principais:
  1. Em r_0, ao ler a, permanece em r_0.
  2. Em r_0, ao ler b, empilha X.
  3. Em r_0, ao ler o primeiro c, vai para r_1.
  4. Em r_1:
    • Ao ler c com topo X, desempilha um X.
    • Ao ler c com topo \bot, vai para r_{f1} (final) e consome o resto de c.
    • Em ε-transição de r_1 para r_{f2} se, no fim da entrada, ainda restar X (esvazia-se e entra em r_{f2}).
  5. Em r_{f1},r_{f2}, para qualquer c, permanece no próprio estado consumindo input.
Os estados finais r_{f1},r_{f2} aceitam exatamente quando j\neq k.

Resposta

L não é regular, pois seu complemento dentro de a^*b^*c^* é \{a^n b^n c^n\}, não regular, e as regulares fecham-se em diferença.
– PDA para \{a^i b^j c^k\mid i\neq j\}: empilha em q_0, desempilha em q_1, vai a dois estados finais q_{f1},q_{f2} conforme j>i ou i>j.
– PDA para \{a^i b^j c^k\mid i\neq k\}: empilha em p_0, desempilha em p_1, vai a dois estados finais p_{f1},p_{f2} conforme k>i ou i>k.
– PDA para \{a^i b^j c^k\mid j\neq k\}: empilha em r_0 durante b, desempilha em r_1, vai a dois estados finais r_{f1},r_{f2} conforme k>j ou j>k.

Exercícios relacionados