PDA com mais de um estado inicial

Question

Estou me perguntando se os PDAs com mais de um estado inicial também estão aceitando idiomas livres de contexto.

se encontrado que Pergunta sobre este site sobre NFASe gostaria de saber se esta resposta também é válida para PDAs se alguém define um novo estado inicial único e conectar isso com os antigos estados iniciais usando $ \ epsilon: \ epsilon \ para \ epsilon$ transições?

Answer 1

PDAs permitidos ter mais de um estado inicial (vamos chamá-los de PDAIS) são computacionalmente equivalentes a PDAs convencionais:

• trivialmente, todo PDA convencional pode ser considerado como um PDAI que tem um estado inicial.
• Cada Pdai pode ser convertido em um PDA equivalente com o processo que você descreve.

Então sim, os PDAFs aceitam exatamente as línguas gratuitas de contexto.

Answer 2

Sim, isso é possível.De fato, se pegamos o não-determinismo dos PDAs, então acabamos com algo que é computacionalmente significativamente mais fraco!