0
$\begingroup$

I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic language contains a PDA that is deterministic.

The language in question is: $L = \{w \in \{a,b\}^* : n_a(w) = n_b(w)\}$

$\endgroup$
  • 1
    $\begingroup$ Is $n_a(w)$ the amount of a's in $w$? $\endgroup$ – Renato Sanhueza Nov 23 '15 at 2:32
  • 2
    $\begingroup$ "the PDA of the language L is not X" -- there are many. Is one given? "language contains an automaton" -- that's misleading terminology. Languages like the one you give contain words. Automata accept languages. Also, regarding your tag choice: the given language is not regular. $\endgroup$ – Raphael Nov 23 '15 at 10:21
1
$\begingroup$

Sure, a deterministic language can trivially be accepted by a nondeterministic PDA. Simplest way to see it is that a deterministic PDA is just a special case of the non-deterministic one. If that isn't enough, for some transition

$\begin{align} \delta(q, a, A) = \{(p, \alpha)\} \end{align}$

you can add the following, without changing the language accepted (the modified PDA isn't deterministic, it is enabled to do completely pointless $\epsilon$ moves):

$\begin{align} \delta(q, \epsilon, A) = \{(q, A)\} \end{align}$

$\endgroup$
0
$\begingroup$

The definition of a deterministic context-free language is that it is a language that is accepted by a deterministic pushdown automaton. Therefore, every deterministic context-free language can be recognized by a PDA that is deterministic. In other words, the answer to your question is "no" (assuming I am understand correctly what you mean by "contain"). See https://en.wikipedia.org/wiki/Deterministic_context-free_language.

$\endgroup$
  • $\begingroup$ Hm. I understand the question to mean, "can deterministic language be accepted by non-deterministic automata"? We'll have to wait for clarification. $\endgroup$ – Raphael Nov 23 '15 at 10:23

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.