How to prove $\{ a^ma^lcb^{m+l}\mid m,l \in N \}$ is not regular using the Pumping Lemma?

Question

I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.

Task:
Prove that $M = \left\{ a^ma^lcb^{m+l}\mid m,l \in N \right\} $ with $\sum =\left\{ a,b,c \right\}$ is not a regular language using the Pumping Lemma.

Here is my try:
First of all I would like to write $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\} $. Is this possible?

Proof: Let $n\in N$ be fixed. Choose the word $w = { a }^{ 2n }c{ b }^{ 2n }\in M$ with $|w|\ge n$. Let $w=xyz$ be a decomposition with $y\neq \lambda $ and $|xy|\le n$. Then we have $x={ a }^{ 2i }$, $y={ a }^{ 2j }$ and $z={ a }^{ 2n-2i-2j }c{ b }^{ 2n }$ for $j\neq 0$ and $2(i+j)\le 2n$.

We choose $k=0$. Then we have $x{ y }^{ 0 }z = { a }^{ 2n-2i }c{ b }^{ 2n }$. $\Longrightarrow x{ y }^{ 0 }z\notin M$ because $2n-2i\neq 2n$ for $j\neq 0$. $\Longrightarrow$ M is not a regular language.

Answer 1

First of all I would like to write $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\} $. Is this possible?

We have $a^ma^\ell cb^{m+\ell}=a^{m+\ell}cb^{m+\ell}$ so you can certainly write that as $a^ncb^n$ for some $n\geq 2$. But you can't write it as $a^{2n}cb^{2n}$ because $m+\ell$ isn't necessarily even.

The question originally contained a typo, as follows. I've kept my answer to that version of the question because it illustrates a common mistake, so will probably be useful to somebody.

First of all I would like to write $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+1 }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\} $. Is this possible?

No, you can't do that. Let $M=\{a^ma^\ell cb^{m+1}\mid m,\ell\in\mathbb{N}\}$ and $M'= \{a^{2n}cb^{2n}\mid n\in\mathbb{N}\}$. Any $a^{2n}cb^{2n}\in M'$ can be rewritten as $a^{(2n-1)}a^1cb^{(2n-1)+1}\in M$ (i.e., we can set $m=2n-1$ $\ell=1$), so $M'\subseteq M$. However, take $m=2$, $\ell=1$ and we get $a^3cb^3\in M$, but this string is not in $M'$, which means that $M'\neq M$.

You've tried to prove that $M'$ is non-regular but that doesn't prove that $M$ is non-regular. For example, pick your favourite non-regular language $L$ over your favourite alphabet $\Sigma$. $L\subsetneq\Sigma^*$ but the fact that $L$ is non-regular certainly doesn't mean that $\Sigma^*$ is non-regular!

Proof.

Your proof that $M'$ is non-regular is basically correct except for two small mistakes. First, you can't assume that $x$ and $y$ have even length: they need to have length $i$ and $j$, rather than $2i$ and $2j$. Remember that you need to show that every partition of the string as $xyz$ fails the pumping property, not just the ones where $x$ and $y$ have some particular property. Second, in your sentences about $xy^0z$, some of the $i$s should be $j$s.