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.
Passo 1
O enunciado pede para mostrar que
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:
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
e depois desempilha verificando se vem .
Passo 2
Prova de que
não é regular usando o lema do bombeamento.
Suponha, por contradição, que seja regular e tenha comprimento de bombeamento
. Considere a string
Suponha, por contradição, que
Note que
com
, logo
.
Pelo lema do bombeamento, existem substrings tais que
Pelo lema do bombeamento, existem substrings
-
, -
, -
, - para todo
, .
Como
, o trecho
fica dentro dos primeiros
símbolos de
, todos iguais a
. Logo
com
.
Considere . Então
Considere
Se essa string fosse de forma
, então ela deveria ter igual número de
antes e depois do centro. Mas aqui há
antes do primeiro
e
após o segundo
, com
. Isso quebra a simetria exigida por
. Portanto
o que contradiz o lema do bombeamento. Concluímos que
não é regular.
Passo 3
Construção do PDA não determinístico
que reconhece
por estado final.
Definimos
Definimos
com
A ideia é: em
empilhamos símbolos lendo a primeira metade
; em algum ponto não determinístico mudamos para
e então, ao ler
, vamos desempilhando; quando a pilha voltar a conter só
e o input acabar, vamos para
.
As transições
são:
- Empilhar em
: para todo ,
- Mudança não determinística para fase de desempilhar:
- Desempilhar em
:
- Aceitar quando a pilha volta a
e o input acabou:
O estado
é final.
Passo 4
Funcionamento resumido:
- Em
, para cada símbolo lido de , ele é empilhado. - A qualquer momento fazemos uma transição
para , marcando o fim de . - Em
, 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ó
, mudamos para e aceitamos.