Showing that a language is regular - Pushdown Automaton

Question

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.

Answer 1

Regular languages are those which can be recognised using only finite memory. Since the PDA for $L$ only ever uses at most the first 200 places of its stack, it is only really using finite memory, even though it has infinite memory available.

While I consider this argument completely convincing, if you are just learning formal language theory it's probably a good exercise to actually write down the proof that you can convert the PDA for $L$ into a FSA recognising the same language.

To get you started on that: Let $A = (Q, q_0, \Sigma, \Gamma, \delta, F)$ be a PDA recognising $L$ (I don't know how you like your PDA specified, let me know if that's not clear), such that at any point when processing a word in $\Sigma^*$, there are at most 200 symbols on the stack of $A$. We want to construct a FSA $B$ recognising $L$. For a start, what should the states of $B$ be? (Note that $A$ has only finitely many 'configurations' it can be in, since it has finitely many states and only uses a finite amount of its stack.)

[Added later, since you asked for more of a hint:]

By the 'configuration' of a PDA, I mean the current state, and the word currently on the stack. So we can represent the configuration by a pair $(q,w)$ with $q\in Q$, $w\in \Gamma^*$ (where $\Gamma$ is the stack alphabet). Except since we only ever have at most 200 symbols on the stack, we can suppose $w\in \cup_{i=0}^{200} \Gamma^i$ (where $\Gamma^i$ means all strings of length $i$ in $\Gamma^*$). So $A$ has finitely many possible configurations, which we can take to be the states of the FSA we are trying to construct.

Now describe the transition function of the FSA.

Answer 2

The stack information is somewhat large but finite. So you can put it in the states of a finite state automaton, and simulate its behaviour that way.