I would like to know why for the recognition of context-free languages only non-deterministic push-down automata (DPA=NPDA) work. Why do deterministic push-down automata (DPDA) not recognize such languages?
$\begingroup$
$\endgroup$
2
-
10$\begingroup$ A language can be recognised by a deterministic pushdown automata iff there exists some LR(1) grammar for that language. As there are context free languages that do not have any LR(1) grammar describing them, NPDA != DPDA. As these results are very well known and will usually get treated in a course on compilers, I'm not sure if that answers your question: are you perhaps looking for intuition behind this fact? $\endgroup$– Alex ten BrinkJan 10, 2012 at 0:31
-
$\begingroup$ it is indeed somewhat counterintuitive given there are other key models where nondeterminism makes no difference on languages accepted-- FSMs and TMs. $\endgroup$– vznJul 4, 2012 at 2:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I'm not quite sure which flavour of "why" you are looking for. One reason for the increase in power when allowing nondeterminism can be seen in the following example:
Let $L$ be the set of palindromes $w\bar{w}$ over some alphabet (of at least two symbols), where $\bar{w}$ is the reverse of $w$. An NPDA for this language can just keep pushing symbols onto its stack, and then at some point guess that it has reached the middle of the input and gradually empty the stack. Note that the acceptance condition is purely existential - it is enough that there is a correct guess for the word to be accepted.
A deterministic PDA would have to choose the position it considers the middle in some way that only depends on the current prefix. Assume $A$ is such a DPDA. For any $k\in\mathbb{N}$, let $u_k=ab^{2k}a$; let $v_0$ be the empty word, and $v_{k+1} = v_ku_kv_k$. This is a sequence of palindromes, each a prefix of the next, so that $A$ must be in an accepting state $q_k$, with the stack empty, after reading $v_k$. By the pigeon hole principle, there must be some $k,l$ such that $k\neq l$ and $q_k=q_l$ (there is a finite number of states, and so some must be 'reused' as there are an infinite number of $k$s). But then $A$ cannot distinguish $v_ku_kv_k$, which is a palindrome, from $v_lu_kv_k$, which isn't.
answered Jan 10, 2012 at 14:10
$\begingroup$
$\endgroup$
FA deterministically or non-deterministically accepts the same language(ie. Regular Lang).
But in case of PDA, if we restrict it to behave deterministically it will not accept some CFLs(CFLs without prefix property (except RLs)).
Why so?
Consider an example of CFL which does not have prefix property(Prefix property of a lang: no string is a proper prefix of another string in the lang).
L= wwr
eg. strings 00 and 0000. (00 is a proper prefix of 0000 thus wwr is not having pref. property).
On occurence of 00 DPDA will go to final state. Now since DPDA has no choice between acceptancy and continuity, it cannot accept 0000 after accepting 00. This is the place where PDA requires non-determinism.
Observations: In case of FA, lang(RL) without pref. property can be accepted deterministically(eg. strings starting with 0). This shows that the effect of prefix property of RL and CFL is different. The difference between determinism and non-determinism for PDA gives rise to a new family of lang. which is accepted by DPDA. This lang is called DCFL.
