Skip to main content
added 83 characters in body
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^*b $$$$ a(a+b)(a+b)^*b, $$ assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^*$). The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

  • ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
  • ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^*b $$ The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

  • ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
  • ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^*b, $$ assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^*$). The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

  • ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
  • ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.
Source Link
Rick Decker
  • 14.9k
  • 5
  • 42
  • 54

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression $$ a(a+b)(a+b)^*b $$ The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

  • ($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
  • ($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have $$ s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$} $$ for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.