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.
é primo
Passo 1
O enunciado pede para mostrar que
não é regular e, em seguida, construir um autômato de pilha (PDA) com aceitação por estado final que reconheça
. Para provar que
não é regular, vamos usar o Lema do Bombeamento para linguagens regulares.
Passo 2
Suponha, por absurdo, que
seja regular. Então existe um inteiro de bombeamento
tal que qualquer cadeia
com
se decompõe em
satisfazendo
-
, -
, - para todo
, .
Passo 3
Como existem fendas arbitrariamente grandes entre primos (ou seja, há
números compostos consecutivos antes de algum primo grande), podemos escolher um primo
de modo que todos os inteiros
sejam compostos. Seja
com
.
Passo 4
Pela condição 1 e 2, a região
está inteiramente entre as primeiras
posições de
, logo
para algum
. Se aplicarmos o bombeamento com
, obtemos
Mas
implica que
é um dos inteiros em
, todos eles compostos. Então
não é primo e, consequentemente,
. Isso contradiz a condição 3 do Lema do Bombeamento.
Passo 5
Concluímos que a hipótese de
ser regular leva a contradição. Logo,
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
.
Resposta
A linguagem
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.