Push Down Automata Using Fixed States

Question

I've been asked to find the PDA for the language L over the alphabet {a,b,c,d} where L={(a^p)(b^2p)(c^r)(d^s)| p,r,s > 0 AND r=s} I have solved it using 5 states but I must solve it using 6 states. Could anyone help me solve it? [1]: https://i.stack.imgur.com/pqYMQ.jpg

Answer 1

Take your 5-state PDA. Let's refer to its start state as q0. Construct a new 6-state PDA as follows:

1. add a new start state q* to your 5-state PDA; so, q0 is still a state in the newly constructed PDA, but it is not longer a start state.

2. add a transition from q* to q0 which requires the bottom-of-stack symbol Z0 to be on the top of the stack (i.e., the stack is empty) and which consumes no input whatever (epsilon/lambda transition).

You now have a 6-state PDA which accepts precisely the same language as your 5-state PDA.

Even simpler: add a new state which transitions to itself on all possible stack/input combinations, and which no other state in the 5-state PDA transitions to. This produces a 6-state PDA that accepts the same language as the 5-state PDA. Sure, the state graph is disconnected now, but I am not sure the state graph being connected by transitions is really a requirement in standard definitions of automata. Of course, it is silly to add states not reachable from the start state, but it is also silly to insist upon a 6-state PDA when you have a perfectly good 5-state PDA.