1
$\begingroup$

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$.

2 Answers 2

2

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.

  • 0
    Well, I don't have any time today to think how to write a nice hint, but hopefully I will tomorrow. In the mean time, keep trying! Doing maths is all about _figuring out_ how to do something you don't already know how to do.2012-11-17
1

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.

  • 0
    It's not that there's a standard method you can apply that you need to know. You just need to think about how you would go about doing it and write that down. Anyway, I'll add a hint to my answer.2012-11-16