1
$\begingroup$

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)

W = {w ∈ {a, b}^* | w contains at least as many as as bs}

My thought process so far has been this:

 1. Start off in q0 (q0 being an accept state)
 2. add a $ to the start of the stack (so you can see when the stack is empty), then transition to q1 (not an accept state).
 3. If you receive an a:
  - if there is an a at the top of the stack, push the a on.
  - if there is a b at the top of the stack, pop the b.
  - if there is nothing on the top of the stack, push the a on.
 4. If you receive a b:
  - if there is an a at the top of the stack, pop the a.
  - if there is a b at the top of the stack, push the b on.
  - if there is nothing on the top of the stack push the b on.
 5. Once there is no more input:
  - if there is a $ at the top of the stack, transition to q3 (q3 being an accept state) - this means there was an equal number of as and bs
  - if there is an a at the top of the stack, transition to q3 (q3 being an accept state) - this means there was more as than bs
  if there is a b at the top of the stack, it means there was more bs than as, and thus we stay in q2, which is not an accept state.

(Sorry if this is hard to understand, I am not sure how to link those transition diagrams of the PDA's I've seen in some posts, if someone can tell me how to create one and link it in the post, I can update the post to be more understandable if needed)

I have a few questions:

  1. Is this approach correct?
  2. Is the it correct to assume the machine is smart enough to know that if there isn't a b at the top of the stack, and I receive an a, it will push that a onto the stack (something like (q1, a, ε) -> (q1, a) to cover both cases where there is an a on the top of the stack and also the case where the stack has nothing in it))
  3. Do I need to push a \$ at the start from q0 to q1 in the transition diagram (I've seen this to be the case for all PDAs on my lecture slide - which makes me think is it necessary to include if all machines need to do this - why is it not just implied?)
  4. I am ok to have 2 different scenarios to go to q2 right? Or would I be better doing something in q1, where if I have reached the end of my input queue, keep popping off as on the top of the stack until I reach the \$, then transition to q2?

Sorry if anything is unclear - I am not super familiar with PDAs and the way to describe things - please let me know if I need to clarify anything.

$\endgroup$

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.