Identification of Formal Language

$$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?

$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

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

-
there is at least one $d$ in $vr$, and

-
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:

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

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

StackExchange Computer Science Q#93428, answer score: 3