Exercício 11. Seja L uma linguagem livre de contexto e
uma linguagem regular. Descreva a construção de um PDA para mostrar como reconhecer a linguagem
e prove que sua construção está correta.
Passo 1
O enunciado pede para mostrar que, se
é livre de contexto e
é regular, então
é livre de contexto. Vamos usar a construção de um autômato de pilha (PDA) que simula em paralelo um PDA que reconhece
e um DFA que reconhece
.
Passo 2
Seja
um PDA que reconhece
, e seja
um DFA que reconhece
. Aqui
é o conjunto de estados do PDA,
o alfabeto de pilha,
sua função de transição, e
é o conjunto de estados do DFA com função de transição
.
Passo 3
Definimos o PDA
que reconhecerá
da seguinte forma:
,
,
.
A ideia é que um estado de
indique “PDA em
” e “DFA em
”.
A ideia é que um estado
Passo 4
Precisamos definir
. Para cada transição de
e cada estado
:
com
e
, então em
temos
Aqui consumimos
na entrada, fazemos a mesma operação na pilha e avançamos o estado do DFA via
.
então
Ou seja, transições-
do PDA original ocorrem sem mudar o estado do DFA.
Dessa forma
consome cada símbolo simulando ao mesmo tempo
e
.
Passo 5
Para provar correção, mostre duas implicações:
Assim
, o que demonstra a correção da construção.
Resposta
O PDA que reconhece
é
com
dada por
Os estados finais são
.