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

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.

• What is your format? (INPUT SYMBOL, TOP-OF-STACK, REPLACEMENT-FOR-TOP)? – Zachary Vance Oct 9 '20 at 14:35
• @ZacharyVance Yes that is the format – 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),
action
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