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 # x: w\right. é uma subpalavra de x, onde \left.x \in\{0,1\}^{*}\right\}.

Passo 1

O enunciado define a linguagem
L = \{\,w\#x \mid w\text{ é uma subpalavra (substring) de }x,\;x\in\{0,1\}^*\}.é
Vamos primeiro mostrar que L não é regular usando o lema do bombeamento e em seguida construir um autômato de pilha não determinístico (AP) que aceite L por estado final.

Passo 2

Prova de que L não é regular pelo lema do bombeamento.
Suponha, por absurdo, que L seja regular. Seja p a constante do lema do bombeamento. Considere a cadeia
s = 0^p\#0^p.
Note que s\in L, pois a parte antes do \# é w=0^p e isso é substring de x=0^p. Pelo lema, podemos escrever s=xyz com
  1. |xy|\le p,
  2. |y|>0,
  3. para todo i\ge0, xy^iz\in L.
    Como |xy|\le p, o trecho y está inteiramente na parte 0^p antes do \#. Logo y=0^k para algum k>0. Se tomarmos i=2, a cadeia bombeada é
s'=xy^2z = 0^{p+k}\#0^p.
Agora a parte antes do \# é 0^{p+k}, que não pode ser substring de 0^p (pois é mais longa). Logo s'\notin L, contradição com o lema do bombeamento. Assim L não é regular.

Passo 3

Ideia do autômato de pilha:
  1. Na fase antes do símbolo \#, empilhamos cada símbolo de w.
  2. Ao ler o \#, mudamos para a fase de busca em x.
  3. Na fase de busca, podemos escolher não começar a correspondência ainda (ignorar símbolos de x) ou, em um momento arbitrário, entrar na fase de matching, onde cada símbolo lido de x deve corresponder ao topo da pilha, que é desempilhado.
  4. Se conseguirmos desempilhar toda a palavra w (stack volta ao símbolo inicial), aceitamos (por estado final), consumindo o restante de x sem alterar a pilha.

Passo 4

Definição formal do AP M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F):
Q = \{q_0,q_1,q_2,q_3\},\quad \Sigma=\{0,1,\#\},\quad \Gamma=\{0,1,Z_0\},
q_0\text{ é o estado inicial},\quad Z_0\text{ é o símbolo de fundo de pilha},\quad F=\{q_3\}.ééí
A função de transição \delta é dada pelas regras abaixo. Em cada bloco exibimos uma só regra, isolada:
\delta(q_0,\,a,\,Z_0)\;=\;(q_0,\,a\,Z_0)\quad\text{para }a\in\{0,1\}
\delta(q_0,\,a,\,b)\;=\;(q_0,\,a\,b)\quad\text{para }a,b\in\{0,1\}
\delta(q_0,\,\#,\,X)\;=\;(q_1,\,X)\quad\text{para }X\in\{0,1,Z_0\}
\delta(q_1,\,a,\,X)\;=\;(q_1,\,X)\quad\text{(ignorar símbolo em }x),\;a\in\{0,1\},\,X\in\{0,1,Z_0\}í
\delta(q_1,\,a,\,a)\;=\;(q_2,\,\varepsilon)\quad\text{(iniciar correspondência)},\;a\in\{0,1\}ê
\delta(q_2,\,a,\,a)\;=\;(q_2,\,\varepsilon)\quad\text{(continuar matching)},\;a\in\{0,1\}
\delta(q_2,\,\varepsilon,\,Z_0)\;=\;(q_3,\,Z_0)\quad\text{(pilha zerada, vamos aceitar)}
\delta(q_3,\,a,\,Z_0)\;=\;(q_3,\,Z_0)\quad\text{(consumir resto de }x\text{ após match)},\;a\in\{0,1\}ó
Nesse AP, qualquer caminho que esvazie a parte empilhada de w em algum ponto de x leva ao estado final q_3, garantindo aceitação exata das cadeias em que w aparece como substring de x.

Resposta

A linguagem
L=\{w\#x\mid w\text{ é substring de }x\}é
não é regular (pela prova do lema do bombeamento) e é reconhecida pelo autômato de pilha M construído acima, que aceita por estado final.

Exercícios relacionados