0
$\begingroup$

Say I had a PDA with alphabet language {0,1}, and a stack language {P,Q,\$}. In the PDA I don't really care what the inputs are at the end and I just want to clear the stack back down to the special character. I could write out the transitions like:

1,P->e

1,Q->e

0,P->e

0,Q->e

e,P->e

e,Q->e

1,\$->\$

0,\$->\$

but that's a bit much. Is it in convention to instead just write:

{0,1},{P,Q}->e

e,{P,Q}->e

{0,1},\$->\$

Note that I'm not trying to pop more than a symbol at a time, just to I don't care about the inputs or stack at this point. With this small alphabet and stack it's not horrible... but if the languages were larger that would be a lot of diction for every individual case. I just want loop on this state to get to a point where the inputs are e and the stack is \$ so that I can transition to the final accept state with e,\$->e

I only ask because I have not seen any textbook or material write transitions as such. So this is either a yes or no answer, or if there's some other convention for how to handle larger alphabets, please let me know what it is.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is technically allowed (its just a shorthand, I believe its understandable, but if you aren't sure, just explain what it represents)

However, one important thing to note is that $\{0,1\}\times \{P,Q\}\rightarrow \epsilon$ is a totally different transision than $\{\epsilon\}\times\{P,Q\}\rightarrow \epsilon$.

The first one would "eat up" a part of the input, for every symbol you delete from the stack (which also means you will delete a bounded number of elements from the stack)

While the second one will just totally empty the stack and will not change the input altogether (and the number of elements deleted here is not bounded).

Usually, the second approach is the better one for clearing the stack, since it:

  1. Clears the entire stack and not only a portion of it
  2. Does not "eat up" the input symbols
Improve this answer
$\endgroup$
5
  • $\begingroup$ Oh, good point on the on ε,{p,q}->ε I was also thinking that maybe it would be clearer if I just defined a subset of Γ for cases where the |Γ | = some huge number. Something like: We could say something like Γ = {A1,A2....An,$}. A ⊆ Γ where A = {x | x ∈ Γ and x =/= $}. then write: Σ, A->ε . does that still read right? Essentially it should be, eat all the inputs, pop the stack until you get to the special character. $\endgroup$
    – SailorFuzz
    Jun 17, 2021 at 18:24
  • $\begingroup$ I believe that writing $\{\epsilon\}\times \{P,Q\}\rightarrow \epsilon$ is more readable. This is usually the convention when you do stuff like that. Since deleting the stack contents is something you do in a lot of problems, it should be clear enough. $\endgroup$
    – nir shahar
    Jun 17, 2021 at 18:28
  • $\begingroup$ Also, what is $\Gamma$ here? $\endgroup$
    – nir shahar
    Jun 17, 2021 at 18:28
  • $\begingroup$ Γ is the stack language. It kind of got cut off/displaced on a new line, but I defined (as an example) that Γ = {A1,A2....An,$} $\endgroup$
    – SailorFuzz
    Jun 17, 2021 at 19:04
  • $\begingroup$ Then just write $\{\epsilon\}\times \Gamma\setminus \{\$\}\rightarrow \epsilon$ $\endgroup$
    – nir shahar
    Jun 17, 2021 at 19:10

Your Answer

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

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