5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think $L$ is context-free; consider $S \to aSbS \mid aSaSbS \mid aSbSaS\mid bSaS \mid bSaSaS \mid \varepsilon$. $\endgroup$ – Raphael Feb 5 '14 at 8:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Even though I cannot understand this answer (I tried so hard..), thank you so much for giving me the hint. I think using that CFG for DK-test would be easier to prove that L has no DPDA. $\endgroup$ – user3273554 Feb 9 '14 at 3:27

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.