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.

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

This works

  • $\begingroup$ 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? $\endgroup$ – Andrew Raleigh Feb 1 '19 at 19:52
  • $\begingroup$ 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 $\endgroup$ – phan801 Feb 1 '19 at 19:58
  • $\begingroup$ 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? $\endgroup$ – Andrew Raleigh Feb 1 '19 at 20:23
  • $\begingroup$ You're right, once ageain. See the edit and let me know if something else doesn't seem right $\endgroup$ – phan801 Feb 1 '19 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.