Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

I have tried to find a pushdown automata and it turned out to be a non-deterministic one.

NPDA for the language

  • 2
    $\begingroup$ What is your format? (INPUT SYMBOL, TOP-OF-STACK, REPLACEMENT-FOR-TOP)? $\endgroup$ – Zachary Vance Oct 9 '20 at 14:35
  • $\begingroup$ @ZacharyVance Yes that is the format $\endgroup$ – user119726 Oct 14 '20 at 8:40

Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples.

  • Keep track of the parity of 'a's you read in two states.
  • If you read 'aa', push A on the stack
  • When you hit b, you better be on odd parity
  • Pop 'A' for every 'b' you read
  • At the end of the input, succeed if the stack is exactly empty.

This accepts only when i == 2j+1. Then, invert the last step, while keeping the requirement to keep it in the format $\{a^ib^j\}$ to get the version below. This requires adding one more state.

This might be a valid formal version, or it might not:

state,      input (z=end-of-string),
               top of stack (E=empty, *=anything),
q_a_even,   a, *, do nothing and transition to q_a_odd
q_a_even,   b, *, transition to q_b_ok
q_a_even,   z, *, succeed
q_a_odd,    a, *, push 'A' and transition to q_a_even
q_a_odd,    b, E, transition to q_b_ok
q_a_odd,    b, A, pop and transition to q_b_danger
q_a_odd,    z, *, succeed
q_b_danger, a, *, fail
q_b_danger, b, E, succeed
q_b_danger, b, A, pop and transition to q_b_danger
q_b_danger, z, A, succeed
q_b_danger, z, E, fail
q_b_ok,     a, *, fail
q_b_ok,     b, *, transition to q_b_ok
q_b_ok,     z, *, succeed

Your Answer

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