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\{0^{p}: p\right. é primo \}

Passo 1

O enunciado pede para mostrar que
L \;=\;\{\,0^{p}\colon p\text{ é primo}\}é
não é regular e, em seguida, construir um autômato de pilha (PDA) com aceitação por estado final que reconheça L. Para provar que L não é regular, vamos usar o Lema do Bombeamento para linguagens regulares.

Passo 2

Suponha, por absurdo, que L seja regular. Então existe um inteiro de bombeamento n\ge1 tal que qualquer cadeia s\in L com |s|\ge n se decompõe em s=xyz satisfazendo
  1. \lvert xy\rvert\le n,
  2. \lvert y\rvert\ge1,
  3. para todo i\ge0, xy^iz\in L.

Passo 3

Como existem fendas arbitrariamente grandes entre primos (ou seja, há n números compostos consecutivos antes de algum primo grande), podemos escolher um primo p>n de modo que todos os inteiros p-1,p-2,\dots,p-n sejam compostos. Seja
s = 0^{p}\in L
com p>n.

Passo 4

Pela condição 1 e 2, a região y está inteiramente entre as primeiras n posições de s, logo \lvert y\rvert = k para algum 1\le k\le n. Se aplicarmos o bombeamento com i=0, obtemos
xy^0z = xz = 0^{\,p-k}.
Mas 1\le k\le n implica que p-k é um dos inteiros em \{p-1,\dots,p-n\}, todos eles compostos. Então \,p-k não é primo e, consequentemente, 0^{p-k}\notin L. Isso contradiz a condição 3 do Lema do Bombeamento.

Passo 5

Concluímos que a hipótese de L ser regular leva a contradição. Logo,
L=\{0^p\colon p\text{ é primo}\}é
não é regular.

Passo 6

Além disso, é conhecido em Teoria da Computação que a linguagem dos números primos em notação unária não é sequer livre de contexto. Portanto, não existe autômato de pilha (PDA) que reconheça L.

Resposta

A linguagem \{0^p\colon p\text{ é primo}\}é não é regular e também não é livre de contexto, de modo que não existe PDA com aceitação por estado final para ela.

Exercícios relacionados