4
$\begingroup$

$$L = \{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\}.$$

Is $L$ DCFL or not?

According to me it should be DCFL since we can write $L$ as $\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\}$. So, now after push and pop on the stack, it will be empty. So, according to me it will be DCFL but I have doubt since DPDA can't count $n$ and $m$ after reading symbol $a$ so machine can't know how many $a$'s should have to be popped. According to this logic, one stack is not enough for this language. So, it should be CSL. Please tell me whether it should be DCFL or CSL?

$\endgroup$
  • 2
    $\begingroup$ Those are not the only two possibilities. It could be context-free but not deterministic (and probably is). $\endgroup$ – rici Jun 24 '18 at 6:20
  • $\begingroup$ @rici , could you please explain how it is CFL , but not DCFL ? $\endgroup$ – user89917 Jun 24 '18 at 6:55
  • 1
    $\begingroup$ Your construction makes it clear how to write a context-free grammar. So it's a CFL. But that grammar is not deterministic. It may be that no deterministic grammar exists in which case the language is not a DCFL. But it's still a CFL. $\endgroup$ – rici Jun 24 '18 at 6:59
  • $\begingroup$ See Wikipedia: en.m.wikipedia.org/wiki/Deterministic_context-free_language which notes that DCFLs are a proper subset of CFLs. $\endgroup$ – rici Jun 24 '18 at 7:01
  • 2
    $\begingroup$ Your PDA has to guess when to switch from $a^n$ to $a^m$. Deterministically, you can read $a^{m+n} b^{m+k}$ and have a representation of $n-k$ on the stack, but I'm not sure how this is helpful (consider for example the case $n=k$). $\endgroup$ – Yuval Filmus Jun 24 '18 at 12:25
3
$\begingroup$

$L$ is CFL because there is a CFG generating it:

$$ \begin{align} S&\rightarrow aAc\\ A&\rightarrow aAc \mid BC\\ B&\rightarrow aDb\\ C&\rightarrow bEc\\ D&\rightarrow aDb \mid \epsilon\\ E&\rightarrow bEc \mid \epsilon \end{align} $$


$L$ is not DCFL. To prove this, we give some lemmas firstly:

Lemma 1. $$ \begin{align} L &=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}\\ &=\{a^x b^y c^{|x-y|+2+z}\mid x,y\ge 2, z\text{ is even},0\le z\le x+y-|x-y|-4\}. \end{align} $$

Proof. Let $L'=\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\}$. Easy to see $L\subseteq L'$. Now let $a^xb^yc^z\in L'$, then we can choose $m=(x+y-z)/2, n=(x-y+z)/2, k=(y-x+z)/2$. Because $x+y+z$ is even, $m,n,k$ are all integers. Because $|x-y|+2\le z\le x+y-2$, we have $m,n,k\ge 1$, so $a^xb^yc^z\in L$. As a result, $L=L'$.

Lemma 2. $M =\{a^x b^y c^{|x-y|+2}d^z\mid x,y\ge 2, z\text{ is even},z\le x+y-|x-y|-4\}$ is not context-free.

Proof. Suppose it is context-free, according to Odgen's lemma, there exists some $p\ge 1$ such that $s=a^{p+2}b^{p+2}c^2d^{2p}\in M$ can be written as $s=uvwrt$, such that

  1. the number of $d$s in $vwr$ is at most $p$ (i.e. we mark all $d$s),

  2. there is at least one $d$ in $vr$, and

  3. for all $q\ge 0$, $uv^qwr^qt\in M$.

From condition 3, $v$ and $r$ each contains at most one character. Together with condition 2, as $q$ grows, the number of $d$s in $uv^qwr^qt$ grows infinitely. To satisfy the condition $z\le x+y-|x-y|-4=2\min\{x,y\}-4$, the number of $a$ and $b$ must both grow, i.e. $a$ and $b$ must both in $vr$. However, $vr$ contains at most two characters, while $d$ is already in it, $vr$ cannot contain both $a$ and $b$, a contradiction.


Now let's come back to $L$. Suppose there is a DPDA $D$ accepting $L$, we create two copies $D_1$ and $D_2$ of $D$ and change the input character $c$ in $D_2$ to $d$. We then construct a new PDA $P$ as follows:

  1. The states of $P$ are the union of states of $D_1$ and $D_2$. The start state of $P$ is the start state of $D_1$. The accepting states of $P$ are the accepting states of $D_2$.

  2. For a transition in $D_1$, if the destination is an accepting state in $D_1$, change the destination to the corresponding state in $D_2$. Other transitions keep unchanged.

Now run $P$ on a string $a^xb^yc^{|x-y|+2}d^z\in M$. According to lemma 1, after reading $a^xb^yc^{|x-y|+2}$, it enters a state in $D_2$ for the first time. Since $a^xb^yc^{|x-y|+2+z}\in L$ according to lemma 1, $P$ will finally accept.

On the other hand, if a string $s$ is accepted by $P$, let $s=s_1s_2$ where after reading $s_1$, $P$ enters a state in $D_2$ for the first time. According to lemma 1, $s_1$ must have the form $a^xb^yc^{|x-y|+2}$ ($x,y\ge 2$). Also, $s_2$ does not contain $c$, and after changing all $d$s in $s_2$ to $c$s, $s_1s_2$ belongs to $L$. This means $s$ must have the form $a^xb^yc^{|x-y|+2}d^z$ where $x+y+|x-y|+2+z$ is even (i.e. $z$ is even) and $|x-y|+2+z\le x+y-2$ (i.e. $z\le x+y-|x-y|-4$). Hence $s\in M$.

As a result, $P$ recognizes $M$, which contradicts to lemma 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy