Your grammar is wrong: you don't generate $0$ and $1$ which are certainly in the language, and you generate $\varepsilon$ which may or may not be in it, depending on the exact formulation. Both are easy to fix and the rest looks fine to me. Can you prove correctness?
In order to get a PDA, there are multiple strategies.
- Use the canonical construction from your grammar.
- Construct a PDA (with smarts).
- Note that the only thing you need to remember is the first symbols.
Thus, finite memory is sufficient; the language is regular.
See vonbrand's answer.
When you construct automata, note the following rules of thumb:
- You need a starting state.
- If your language is not empty, you need (reachable) accepting states.
- If your language is not finite, you need loops.
Your automaton already fails on these counts. Instead of succumbing to the formal model, try this: write a regular program that accepts the language, with the following restrictions:
- You can only use one
while loop, no recursion.
- You have one stack (with
isempty?, nothing else)¹.
- You have one pointer in the input string, and it can only move to the right.
- You can only have a fixed (i.e. independent of the input) number of boolean
If you have this, rewrite the program in automaton form; the main task will be to figure out the states from the possible values of your variables.
Be aware that this strategy only works to obtain deterministic automata. Non-deterministic ones are often smaller/simpler, or even necessary (e.g. for inherently ambiguous context-free languages), so you have to become comfortable in the model at some point. This is merely a stepping stone.
- If you disallow the stack, too, the same works for DFA.