# Allowing an empty (epsilon) transition in a PDA

I'm trying to allow an empty transition in a PDA for the following language:

• Alphabet: $$Σ = \{a, b, c\}$$
• Language: $$L = \{ a^ib^j \mid i \neq j \} \cdot \{ c \}^\ast$$

Examples of words in $$L$$:

• $$\varepsilon$$
• $$aabccc$$
• $$abbccc$$

Not in $$L$$:

• $$abcc$$
• $$aabbc$$

Here is what I came up with: The diagram above uses JFLAP - where the symbol $$Z$$ reflects the empty stack. The symbol $$λ$$ is the empty symbol $$ϵ$$.

It accepts everything as it should, but I don't know how to let epsilon get through. q7 to q8 is when there is more b than a. So there should be a way to allow q7 to q9 where a is more than b but also epsilon can get through. Thoughts? I would like to simply set epsilon through but than aabbc can get through easily enough.

• With letting "epsilon get through" do you mean accepting the empty word? Feb 1, 2019 at 15:31
• @dkaeae Sorry yeah, meant accepting the empty word Feb 1, 2019 at 15:41
• @Apass.Jack You're right, fixed to clarify Feb 1, 2019 at 15:43
• Is the $x,y;z$ notation on the state transitions supposed to mean the PDA reads input symbol $x$ and stack symbol $y$ followed by writing $z$ to the stack? Then why is there a symbol $Z$ in the transition from $q_7$ to $q_8$ being read from the stack (if no such symbol was pushed previously)? Feb 1, 2019 at 16:18
• Is $Z$ used to symbolize the end of the stack? Do you use $\lambda$ as $\epsilon$? Feb 1, 2019 at 16:28

Some key points:

• The only case where you want to accept $$\epsilon$$ is when you haven't had any other input and your stack is empty. Therefore you need an accepting state right at the beginning.
• You need to take into consideration inputs such as: $$bac, aac,...$$ that will never result in an accepting state, or $$abbb$$ that results in an accepting state without containing any $$c$$'s
• If you get a $$b$$ and your stack is empty you have more $$b$$'s than $$a$$'s so you need an accepting state
• If you get a $$c$$ and and your stack is not empty you have more $$a$$'s than $$b$$'s so you need an accepting state
• You reject everything else. • Didn't think it would be this complicated, thanks! I do question how $λ, Z : Z$ works? Wouldn't this mean we can put anything in (i.e. a) and it would then accept it? If that's the case would an epsilon transition between $q7$ and $q9$ work as well? Feb 1, 2019 at 19:52
• I'm sorry, you're right! You don't need $\lambda,Z : Z$ at all. You just enter at $q_0$ which is an accepting state. I'll edit Feb 1, 2019 at 19:58
• Another question, from $q4$ to $q5$, does having the $λ, λ:λ$ transition mean anything can go there? Would that mean you can sneak in an $a$ in there and get it accepted? Feb 1, 2019 at 20:23
• You're right, once ageain. See the edit and let me know if something else doesn't seem right Feb 1, 2019 at 20:42