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$.
Showing that a language is regular - Pushdown Automaton
2 Answers
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.
-
0The states of B should be the symbols on the stack of A, right? – 2012-11-16
-
0Something sort of in that direction. Try writing things down and thinking about it for a bit. – 2012-11-16
-
0does it have some 200! states by any chance? So for every combination of stack contents the FA accepts the input? – 2012-11-17
-
0What would your 200! states be? Don't forget that there are probably the states of the PDA to take into account as well as the content of the stack (but you could work with the assumption that the PDA has a single state if that helps simplify things for you). I don't understand what you mean by the second question. You want the FA to accept exactly the same inputs as the PDA accepts. – 2012-11-17
-
0In my mind 200! comes from all the possible permutations of the stack contents, therefore in order for the FA to accept every one, it should have all these permutations as states linked one to another. I believe that I do not know enough theory in order to think this through though :( – 2012-11-17
-
0You definitely don't need to know any theory beyond the definitions of pushdown automata and finite automata. You are already thinking in the right direction. See if having the assurance that you do have the knowledge necessary to prove this helps, and if not I can give a stronger hint. But I'm quite convinced you can get it. Writing down your ideas in detail should help a lot. – 2012-11-17
-
0Thanks for having faith in me Tara. I do not know how to proceed with the proof, and I would appreciate a bit more guidance. – 2012-11-17
-
0Well, 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
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.
-
0I was thinking that because the information needed to be stored on the stack is finite, we could have a PDA that accepts the language, but that doesn't sound like a complete proof. I was wondering if there is more to it than saying that yes, you could build a PDA. – 2012-11-16
-
0@Alex: Presumably you mean FSA (finite state automaton) rather than PDA in that comment? – 2012-11-16
-
0(you mean PDA $\to$ FSA) What is a complete proof depends on the intended audience, how formal they are, how fussy about details. It convinces me. – 2012-11-16
-
0Alex, you should definitely try writing down the details of how you would construct a FSA from the PDA for $L$. You could even write it here as an answer for people to check, if you like. – 2012-11-16
-
0I am not aware of the method to convert a PDA to a FSA, though that seems what I need to do, a proof by construction. Would you mind pointing me to some resources showing such an example? – 2012-11-16
-
0It'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