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\{w w^{R}: w \in\{a, b, c\}^{*}\right\}

Passo 1

O enunciado pede para mostrar que
\displaystyle L = \{\,w\,w^{R} \mid w \in \{a,b,c\}^*\}
não é uma linguagem regular e, em seguida, construir um autômato de pilha (PDA) que a reconheça por estado final.
Conteúdo principal:
  • Lema do bombeamento (pumping lemma) para provar não regularidade;
  • Construção de um PDA não determinístico que empilha a primeira metade de w e depois desempilha verificando se vem w^R.

Passo 2

Prova de que L não é regular usando o lema do bombeamento.
Suponha, por contradição, que L seja regular e tenha comprimento de bombeamento p. Considere a string
s = a^p\,b\,b\,a^p.
Note que s = w\,w^R com w = a^p\,b, logo s\in L.
Pelo lema do bombeamento, existem substrings x,y,z tais que
  1. s = x\,y\,z,
  2. \lvert x y\rvert \le p,
  3. \lvert y\rvert > 0,
  4. para todo i\ge0, x\,y^i\,z\in L.
Como \lvert x y\rvert \le p, o trecho y fica dentro dos primeiros p símbolos de s, todos iguais a a. Logo y = a^k com 1\le k\le p.
Considere i=0. Então
x\,y^0\,z = a^{p-k}\,b\,b\,a^p.
Se essa string fosse de forma u\,u^R, então ela deveria ter igual número de a antes e depois do centro. Mas aqui há p-k a antes do primeiro b e p a após o segundo b, com k>0. Isso quebra a simetria exigida por u\,u^R. Portanto
x\,y^0\,z \notin L,
o que contradiz o lema do bombeamento. Concluímos que L não é regular.

Passo 3

Construção do PDA não determinístico M que reconhece L por estado final.
Definimos
M = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)
com
Q = \{q_0,q_1,q_f\},\quad \Sigma = \{a,b,c\},\quad \Gamma = \{a,b,c,Z_0\},\quad F = \{q_f\}.
A ideia é: em q_0 empilhamos símbolos lendo a primeira metade w; em algum ponto não determinístico mudamos para q_1 e então, ao ler w^R, vamos desempilhando; quando a pilha voltar a conter só Z_0 e o input acabar, vamos para q_f.
As transições \delta são:
  1. Empilhar em q_0: para todo Z\in\Gamma,
\delta(q_0,a,Z)\ni(q_0,aZ),\quad \delta(q_0,b,Z)\ni(q_0,bZ),\quad \delta(q_0,c,Z)\ni(q_0,cZ).
  1. Mudança não determinística para fase de desempilhar:
\delta(q_0,\varepsilon,Z)\ni(q_1,Z) \quad\text{para todo }Z\in\Gamma.
  1. Desempilhar em q_1:
\delta(q_1,a,a)\ni(q_1,\varepsilon),\quad \delta(q_1,b,b)\ni(q_1,\varepsilon),\quad \delta(q_1,c,c)\ni(q_1,\varepsilon).
  1. Aceitar quando a pilha volta a Z_0 e o input acabou:
\delta(q_1,\varepsilon,Z_0)\ni(q_f,Z_0).
O estado q_f é final.

Passo 4

Funcionamento resumido:
  • Em q_0, para cada símbolo lido de w, ele é empilhado.
  • A qualquer momento fazemos uma transição \varepsilon para q_1, marcando o fim de w.
  • Em q_1, a cada símbolo lido, esperamos que seja igual ao topo da pilha e então desempilhamos.
  • Se ao final do input a pilha contiver só Z_0, mudamos \varepsilon para q_f e aceitamos.

Resposta

L não é regular (pelo lema do bombeamento) e o PDA M acima reconhece L por estado final.

Exercícios relacionados