I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL.
Are there any other techniques that will help me to prove a language L is not DCFL?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Well, using other closure properties of DCFL would work similarly, but I'm guessing you are after something else? Are you aware of direct proofs? (I guess most will have the form "assume $L$ was DCFL", anyway.) $\endgroup$– RaphaelFeb 11, 2015 at 11:37
-
2$\begingroup$ The accepted answer to cs.stackexchange.com/questions/10974/… is also relevant here. $\endgroup$– Klaus DraegerFeb 11, 2015 at 15:36
-
$\begingroup$ Thanks for your reply @Raphael.But I don't know the direct proofs.Can you please tell me or send me some link where I can find some examples of direct proof. $\endgroup$– anand nayakFeb 12, 2015 at 6:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
There is a direct type of argument, related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). Then if one input string is the prefix of another, the computation for the longer string must have the shorter computation as prefix. Thus, the computation accepts at (at least) two moments.
As an example, $\{ a^n b^m \mid n\ge1, m=n \mbox{ or } m=2n \}$ is not DCFL; which is seen as follows.
Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewire $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\{ a^nb^nc^n\mid n\ge 1\}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.
answered Feb 17, 2015 at 0:45
-
$\begingroup$ Changing the automaton in such proofs is dangerous. In particular, it's not completely clear why the new automaton accepts this language. The usual way would be to create a contradicting compution in the original $\mathcal{A}$. $\endgroup$– RaphaelFeb 17, 2015 at 7:43
-
1$\begingroup$ I saw this quite a while ago, but didn't get it until now, so I'd like to elaborate in case someone else has questions. It is helpful to think why this rewiring does not work for a DPDA accepting the language $\{a^nb^{2n}:n\in\mathbb{N}\}$ (which exists). The key idea why this does work for $\{a^nb^n, a^nb^{2n}\}$ is that any state corresponding to $a^nb^n$ for any $n$ can only be reached upon reading $a^mb^m$ for some $m$, by virtue of it being an accepting state. Hence we guarantee after this rewiring, we can only traverse from $\mathcal{A}$ to its copy after reading $a^mb^m$. $\endgroup$ Jul 13, 2022 at 12:59