Skip to main content
Computer Science

Return to Question

Post Closed as "Needs details or clarity" by Raphael
edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
added 6 characters in body
Source Link
asdf
asdf
  • 247
  • 1
  • 8

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state. This means means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for thatthe first state). Am I right?

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state. This means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for that state). Am I right?

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state. This means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for the first state). Am I right?

Source Link
asdf
asdf
  • 247
  • 1
  • 8

Are all PDA equivalent to two-state-PDA?

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This algorithm use the first state for all the computation, with rules based on the stack and the input symbol, and when the stack is empty goes to a final state. This means that, for all the generic PDAs we can create a minimal PDA with only two states (and a lot of rules for that state). Am I right?