[Solved]: How to find a Deterministic PDA for an intersection of languages

Problem Detail: 

There are two languages,

$\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and
$\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$

where $N_a$ means the number of occurrences of $a$ in the string $w$. Same for $N_b$.

I've proved that $L_1$ has a DPDA (hope this is right).

Now I want to know whether $L=L_1\cap L_2$ has a DPDA or not.

I applied the Pumping lemma but it seems like there is no contradiction. I tried to draw the DPDA but failed. Maybe $L$ has a nondeterministic PDA but not a DPDA. However I cannot prove this.

Could anyone give me some hints?

Asked By : user3273554

Answered By : FrankW

Your conjecture is right. $L$ is context-free, but not deterministic context-free.

To see that it is context-free, take a repaired verion of the grammar from @Raphael's comment: $S \rightarrow aSbS ~|~ bSaS ~|~ aSbSbS ~|~ bSaSbS ~|~ bSbSaS ~|~ \epsilon$.

Now, assume there is a DPDA $A$ that accepts $L$, and consider words of the form $b^na^m$.

Since the set of suffixes that complete $b^n$ to a word in $L$ differs for each $n$ and $A$ is a DPDA, we can conclude that after reading $b^n$, $n$ larger than some threshold $n_0$, $A$ will be in a state $q_n$ with stack contents of the form $\gamma' \gamma^{i_n} \gamma_n$ and the size of all $\gamma_n$ is bounded by a constant.

Now we group the numbers $n>n_0$ into equivalence classes, based on $q_n$ and $\gamma_n$. Since there are only finitely many equivalence classes, at least one of the equivalence classes wil contain infinitely many values. In the following, we only consider values from this equivalence class $C$.

Now assume, there is $n_1 \in C$, so that when reading $a^{n_1}$ $A$ will go from stack $\gamma'\gamma^{i_{n_1}}\gamma_{n}$ and state $q_n$ to stack $\gamma'\gamma\gamma_{n_1}'$ and state $q_{n_1}'$ without looking at $\gamma'$. Since $b^{n_1}a^{n_1}\in L$, $q_{n_1}$ is accepting. However, since $A$ did not look at $\gamma'$, it will perform the same computation, if it starts reading $a^{n_1}$ with stack contents $\gamma'\gamma^{i_{n_2}}\gamma_n$, $i_{n_2}>i_{n_1}$. By the infiniteness of $C$, it contains $n_2>n_1$ with $i_{n_2}>i_{n_1}$. Thus $A$ would accept $b^{n_2}a^{n_1} \notin L$. So, such an $n_1$ can not be in $C$.

From the previous observation, we can conclude that for each $n_i\in C$ there is a value $n_i'<n_i$, so that after reading $b^{n_i}a^{n_i'}$, $A$ is in a state $q_{n_i}'$ and $A$'s stack contains $\gamma'$. Since $C$ contains infinitely many values $n_i$, we can find $n_1<n_2\in C$ so that $q_{n_1}' = q_{n_2}'$. Now we distinguish 2 cases:

• If $n_1-n_1' > n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')} \notin L$, but since $A$ can not distinguish, if it has read $b^{n_1}a^{n_1'}$ or $b^{n_2}a^{n_2'}$ and $b^{n_2}a^{n_2'+(n_2-n_2')} \in L$, $A$ can not handle both words correctly.
• If $n_1-n_1' \leq n_2-n_2'$, $b^{n_1}a^{n_1'+(n_2-n_2')+n_2} \notin L$, while $b^{n_2}a^{n_2'+(n_2-n_2')+n_2} \in L$, and as in the other case $A$ can not distinguish them.

Thus, such an $A$ can not exist.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21309