<p><strong>FA</strong> deterministically or non-deterministically accepts the same language(ie. Regular Lang).</p>

<p>But in case of <strong>PDA</strong>, if we restrict it to behave <strong>deterministically</strong> it will not accept some CFLs(CFLs <strong>without prefix property</strong> (except RLs)).</p>

<p>Why so?</p>

<p>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).</p>

<p><strong>L= wwr</strong></p>

<p>eg. strings <strong>00</strong> and <strong>0000</strong>. (00 is a proper prefix of 0000 thus wwr is not having pref. property).</p>

<p>On occurence of <strong>00</strong> DPDA will go to final state. Now <strong>since DPDA has no choice between acceptancy and continuity</strong>, it cannot accept <strong>0000</strong> after accepting <strong>00</strong>.
This is the place where PDA requires <strong><em>non-determinism</em></strong>.</p>

<p><strong>Observations</strong>: In case of FA, lang(RL) without pref. property can be accepted deterministically(eg. strings starting with 0). 
This shows that the <strong>effect of prefix property of RL and CFL is different</strong>.
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 <strong>DCFL</strong>.</p>

CC BY-SA 3.0
2015-12-25T06:50:21.817Z
2015-12-25T06:50:21.817Z
Sushant Shinde
<p>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:</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-10T14:10:26.893Z
2012-07-04T13:19:05.200Z
2012-07-04T13:19:05.200Z
Klaus Draeger
<p>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?</p>

CC BY-SA 3.0
2012-01-10T00:31:42.213Z
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?
Alex ten Brink
CC BY-SA 3.0
2012-07-04T02:22:26.660Z
it is indeed somewhat counterintuitive given there are other key models where nondeterminism makes no difference on languages accepted-- FSMs and TMs.
vzn
<fl.formal-languages><automata-theory><context-free>
Why is non-determinism (Push-down automata) necessary?
Reactormonk
# Why is non-determinism (Push-down automata) necessary?

(Asked by: username_0 on 2012-01-09)

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?

**Tags:** fl.formal-languages, automata-theory, context-free

> **Comments:**
> **username_1**: 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?  
> **username_2**: it is indeed somewhat counterintuitive given there are other key models where nondeterminism makes no difference on languages accepted-- FSMs and TMs.  

---

## 2 answers

### Answer by username_4 on 2012-01-10. Score: 25 | Accepted answer

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.


---

### Answer by username_3 on 2015-12-25. Score: 0

**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**.


---

