Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into acceptance by an empty stack? If yes, then what is the procedure of converting PDA (acceptance by final state) into PDA (acceptance by empty stack).

Here is the question. Convert the following PDA to a context-free grammar. P = ({q, p}, {0, 1}, {Z0, X}, δ, q, Z0, {p}) has the following transition function:

  1. δ(q, 0, Z0) ={(q, XZ0)}
  2. δ(q, 0, X) = {(q, XX)}
  3. δ(q, 1, X) = {(q, X)}
  4. δ(q, ε, X) = {(p, ε)}
  5. δ(p, ε, X) = {(p, ε)}
  6. δ(p, 1, X) = {(p, XX)}
  7. δ(p, 1, Z0) = {(p, ε)}

Any help shall be highly appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.