0
$\begingroup$

for a transition $\delta(q,\sigma,X)$, if I keep state $q$ and input symbol $\sigma$ same but read different stack symbols in place of $X$ will it still be called deterministic PDA because as per my understanding for PDA to be deterministic this whole set should contain at most one element. So, is it allowed if I read different stack symbol but same input and same state? the transition will also occur at same state

as a side note I am trying to create a deterministic PDA for accepting valid brackets of all 3 types; {,[,( and for opening brackets I want to make a transition to similar states no matter what the stack symbol is.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Nondeterminism in this context means you can go to two or more different states (or write stack updation) on the same current status (state + input + stack symbol). In your case, you are basically talking about something like this: $\delta(q,\sigma, X) ~~ \forall X\in S$. This in itself is purely deterministic. $\endgroup$
    – codeR
    Commented May 14 at 10:20
  • $\begingroup$ @codeR, that sounds like an answer to the question. Can I encourage you to write that in the 'Your Answer' box rather than as a comment, so we can upvote it and the question can be treated as answered? No need to write any more than that. The site discourages putting answers in the comment field. Thank you! $\endgroup$
    – D.W. ♦
    Commented May 14 at 18:46

1 Answer 1

Reset to default
1
$\begingroup$

Recall the definition of a non-deterministic PDA (NPDA) where the transition function has a mapping $\delta: Q \times (\Sigma \cup \{\lambda\}) \times \Gamma \rightarrow 2^{Q \times \Gamma^*}$ in contrast to $\delta: Q \times (\Sigma \cup \{\lambda\}) \times \Gamma \rightarrow Q \times \Gamma^*$ like in deterministic PDA (DPDA).

So if you consider the state transition diagram on a state $q\in Q$ reading some input $\sigma \in \Sigma$ with stack top symbol being $x \in \Gamma$, you may go to more than one state and/or do more than one stack operation as your $\delta(q,\sigma,x)$ is now a set of tuples in NPDA (not a single tuple as in DPDA).

What you are asking are different entries of the delta function, e.g., $\delta(q,\sigma,x), \delta(q,\sigma,y), \dots$ which have nothing to do with non-determinism. Even in DPDA, we might have such multiple entries for the same $q$ and $\sigma$ but different stack symbols.

Improve this answer
$\endgroup$

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.