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.
ou
ou
Passo 1
O enunciado pede para a linguagem
sobre o alfabeto
. Primeiro vamos provar que
não é regular. Em seguida, para cada uma das três condições
-
, -
, -
,
vamos construir um autômato de pilha (PDA) que reconheça exatamente:tal que a condição correspondente valha , com aceitação por estado final.
Passo 2
Prova de que
não é regular por fechamento de linguagens regulares:
- É sabido que
é regular. - Note que o complemento de
dentro de é e essa última linguagem não é regular (pode‐se provar por pumping lemma). - As linguagens regulares são fechadas sob diferença com outra regular. Se
fosse regular, então seria regular, contradizendo o fato de não ser regular.
Logo,não é regular.
Passo 3
PDA para
.
Intuição: empilhar um para cada
, depois desempilhar um
para cada
.
Intuição: empilhar um
- Se ao ler um
não houver para desempilhar, então : vamos para um estado final e só consumimos o resto de e de . - Se, ao terminar de ler todos os
(isto é, chegar ao primeiro ou ao fim), ainda restar na pilha, então : mudamos para outro estado final e consumimos o resto de .
Descrição dos estados e transições (pilha inicia comno fundo):
Estados:(inicial), , , .
Alfabeto de pilha:.
Transições
:
- Em
, ao ler e ver topo ou , empilha :
,
. - Em
, ao ler o primeiro , vai para sem mexer na pilha. - Em
: - Ao ler
e ver topo , desempilha:
. - Ao ler
e ver topo , não há para desempilhar ⇒ . Transita para (final) e mantém . - Ao ler
em : - Se topo é
, desempilha tudo remanescente de em transição-ε para (final). - Se topo é
, chegamos a ; mas nesse caso não há transição para estado final, então a cadeia é rejeitada.
- Se topo é
- Ao ler
- Em
e , para qualquer ou , permanece no próprio estado consumindo o símbolo e sem tocar a pilha.
Os dois estados
são finais e garantem que aceitamos exatamente quando
.
Passo 4
PDA para
.
Intuição: empilhar em cada
, ignorar
, depois desempilhar em cada
.
Intuição: empilhar
- Se na fase de
vier um com topo , então : vamos para estado final e consumimos o resto de . - Se ao terminar a entrada ainda restar
na pilha, então : mudamos para um estado final.
Estados:
(inicial),
,
,
.
Transições principais:
Transições principais:
- Em
, ao ler , empilha . - Em
, ao ler , permanece em sem mexer na pilha. - Em
, ao ler o primeiro , vai para . - Em
: - Ao ler
com topo , desempilha um . - Ao ler
com topo , transita para (final) e consome o resto de . - Em ε-transição de
para se ao final da entrada ainda restar na pilha (passo-ε que esvazia toda pilha de e entra em ).
- Ao ler
- Em
, para qualquer , permanece no próprio estado consumindo input.
Os estados finais
capturam exatamente as duas possibilidades
ou
.
Passo 5
PDA para
.
Intuição: ignorar , empilhar
em cada
, depois desempilhar em cada
.
Intuição: ignorar
- Se ao ler um
não houver na pilha, então : vamos a um estado final. - Se ao final da entrada restar
, então : indo a outro estado final.
Estados:
(inicial),
,
,
.
Transições principais:
Transições principais:
- Em
, ao ler , permanece em . - Em
, ao ler , empilha . - Em
, ao ler o primeiro , vai para . - Em
: - Ao ler
com topo , desempilha um . - Ao ler
com topo , vai para (final) e consome o resto de . - Em ε-transição de
para se, no fim da entrada, ainda restar (esvazia-se e entra em ).
- Ao ler
- Em
, para qualquer , permanece no próprio estado consumindo input.
Os estados finais
aceitam exatamente quando
.
Resposta
–
não é regular, pois seu complemento dentro de
é
, não regular, e as regulares fecham-se em diferença.
– PDA para : empilha em
, desempilha em
, vai a dois estados finais
conforme
ou
.
– PDA para : empilha em
, desempilha em
, vai a dois estados finais
conforme
ou
.
– PDA para : empilha em
durante
, desempilha em
, vai a dois estados finais
conforme
ou
.
– PDA para
– PDA para
– PDA para