Como posso combinar 2 PDA em 1

Question

Eu preciso formar PDA para este idioma: { $ a ^ nb ^ m | n= m \ vee n= 2m $ }

Eu sei a ideia de construir cada um separadamente, mas como faço para combiná-los em 1 PDA?

lhs: para cada 'a' eu empurro 'a' pilha dentro e para cada 'b' eu eject 'A'.

RHS: Para cada 'A' eu empurro 'A' pilha dentro e para cada 'b' eu ejecti 2 vezes 'a'.

Como posso combiná-los?Posso de alguma forma usar não determinismo?

Answer 1

Construa um PDA para $ n= m $ e outro para $ n= 2m $ .Ramificação para um deles usando uma $ \ epsilon $ transição no início.