Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
The states of B should be the symbols on the stack of A, right? –  Alex Nov 16 '12 at 23:32
    
Something sort of in that direction. Try writing things down and thinking about it for a bit. –  Tara B Nov 16 '12 at 23:32
    
does it have some 200! states by any chance? So for every combination of stack contents the FA accepts the input? –  Alex Nov 17 '12 at 0:27
    
What 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. –  Tara B Nov 17 '12 at 0:35
    
In 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 :( –  Alex Nov 17 '12 at 0:48
show 3 more comments

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.

share|improve this answer
    
I 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. –  Alex Nov 16 '12 at 22:10
    
@Alex: Presumably you mean FSA (finite state automaton) rather than PDA in that comment? –  Tara B Nov 16 '12 at 22:15
    
(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. –  Hendrik Jan Nov 16 '12 at 22:16
    
Alex, 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. –  Tara B Nov 16 '12 at 22:23
    
I 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? –  Alex Nov 16 '12 at 22:57
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.