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.

For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the diagram that starts at q and ends at q, and there is not path from q to and end state.

Essentially, I'm trying to prove that a PDA does not need looping states to create an infinite language but I do not know the first place to start. I know that a PDA can make use of lambda transitions which could possibly be to my benefit, and I know that there can be multiple paths resulting from the same transition but I cannot wrap my head around an infinite number of possibilities without any sort of loop. I suppose I'm not looking for a definitive answer, more so something to get me pointing in the right direction.

Thanks!

share|improve this question
    
"no state q such that q is reachable from the start state, there is no cycle within the diagram that starts at q and ends at q, and there is not path from q to and end state" seems to mean: "Every reachable state is either in a cycle, or can reach the end state (or both)". Is that the intended conditition? (If so, it is easy to enforce for any automaton: Just identify all states that cannot reach the end, and replace all their transition with a self-loop for each symbol in the alphabet. This clearly doesn't change the accepted language). –  Henning Makholm Dec 12 '12 at 21:38
    
It turns out, it was a trick question. I had thought the question was asking to create a state diagram where there were no loops AND the language was infinite. Instead it was to show that a PDA state diagram can have looping states whose conditions for reaching the accept state are impossible (i.e. popping a character that is not in the language) but are still connected to the final state. –  Tom Dec 15 '12 at 1:59

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.