2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks, Lisa! Now I see that you're not just asking for your work to be checked but you do have a specific question about your attempt, so I've answered it. $\endgroup$ – David Richerby Jan 18 at 10:50
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 18 at 11:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I have to say sry, because I had a mistake in M the exponent of b should not be m+1 it should be m+l (L). $\endgroup$ – Lisa.Neust Jan 18 at 11:03
  • $\begingroup$ Aha! That's why it's best to use \ell instead of l in LaTeX, as it's harder to mis-read. In that case, you can absolutely write $a^ma^\ell cb^{m+\ell}$ as $a^ncb^n$. But you can't write $a^{2n}cb^{2n}$ because $m+\ell$ isn't necessarily even. $\endgroup$ – David Richerby Jan 18 at 11:07
  • $\begingroup$ Than I have two more questions. 1) The word I choose can no be $a^{2n}cb^{2n}$ but how can I find a word for this proof? 2) I do not understand why i cant write $2i$ and $2j$. In my old Proof where the word is $a^{2n}cb^{2n}$, I need to write $2i$ and $2j$, or am i wrong? $\endgroup$ – Lisa.Neust Jan 18 at 11:14
  • $\begingroup$ @Lisa.Neust 1) Just use $a^kcb^k$ for any $k>n$. Nothing in your argument needs any length to be even. 2) You can't write $2i$ and $2j$ because you have to prove that every splitting of the word into $xyz$ fails, and you're only proving the cases where $x$ and $y$ have even length. Every case includes all the ones where $x$ and/or $y$ have odd length, too. $\endgroup$ – David Richerby Jan 18 at 11:18
  • $\begingroup$ Oh ok, so i can choose the word as I like? And with just i and j i can proof odd and even numbers at the same time? this makes sense. $\endgroup$ – Lisa.Neust Jan 18 at 11:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.