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$ Feb 1 '19 at 15:41
  • $\begingroup$ @Apass.Jack You're right, fixed to clarify $\endgroup$ 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$ 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$ 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.