# 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? – dkaeae Feb 1 '19 at 15:31
• @dkaeae Sorry yeah, meant accepting the empty word – Andrew Raleigh Feb 1 '19 at 15:41
• @Apass.Jack You're right, fixed to clarify – Andrew Raleigh Feb 1 '19 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)? – dkaeae Feb 1 '19 at 16:18
• Is $Z$ used to symbolize the end of the stack? Do you use $\lambda$ as $\epsilon$? – phan801 Feb 1 '19 at 16:28

• 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
• 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? – Andrew Raleigh Feb 1 '19 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 – phan801 Feb 1 '19 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? – Andrew Raleigh Feb 1 '19 at 20:23