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.
é uma subpalavra de
, onde
.
é uma subpalavra de
Passo 1
O enunciado define a linguagem
Vamos primeiro mostrar que
não é regular usando o lema do bombeamento e em seguida construir um autômato de pilha não determinístico (AP) que aceite
por estado final.
Passo 2
Prova de que
não é regular pelo lema do bombeamento.
Suponha, por absurdo, que seja regular. Seja
a constante do lema do bombeamento. Considere a cadeia
Suponha, por absurdo, que
Note que
, pois a parte antes do
é
e isso é substring de
. Pelo lema, podemos escrever
com
-
, -
, - para todo
, .
Como, o trecho está inteiramente na parte antes do . Logo para algum . Se tomarmos , a cadeia bombeada é
Agora a parte antes do
é
, que não pode ser substring de
(pois é mais longa). Logo
, contradição com o lema do bombeamento. Assim
não é regular.
Passo 3
Ideia do autômato de pilha:
- Na fase antes do símbolo
, empilhamos cada símbolo de . - Ao ler o
, mudamos para a fase de busca em . - Na fase de busca, podemos escolher não começar a correspondência ainda (ignorar símbolos de
) ou, em um momento arbitrário, entrar na fase de matching, onde cada símbolo lido de deve corresponder ao topo da pilha, que é desempilhado. - Se conseguirmos desempilhar toda a palavra
(stack volta ao símbolo inicial), aceitamos (por estado final), consumindo o restante de sem alterar a pilha.
Passo 4
Definição formal do AP
:
A função de transição
é dada pelas regras abaixo. Em cada bloco exibimos uma só regra, isolada:
Nesse AP, qualquer caminho que esvazie a parte empilhada de
em algum ponto de
leva ao estado final
, garantindo aceitação exata das cadeias em que
aparece como substring de
.
Resposta
A linguagem
não é regular (pela prova do lema do bombeamento) e é reconhecida pelo autômato de pilha
construído acima, que aceita por estado final.