Allowing an empty (epsilon) transition in a PDA

Question

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.

Answer 1

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.