1
$\begingroup$

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!

  • 0
    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.2012-12-15

0 Answers 0