1
$\begingroup$

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:

PDA

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.

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

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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