Proving languages are not regular.

[JamesBwoii]

Hi, I am struggling with the concept of proving languages are not regular. I know that I need to use pumping lemma to prove it by contradiction but I can't get my head around it.

Here is one language that I need to prove is not regular.

http://i.imgur.com/quD26In.png

I know that is essentially saying:

a^2^n such that n is greater than or equal 0 is a subset of a*

I know for a language to be regular there exists an integer n > 0 such that any word \in L with \left| w \right| > n can be represented as w = xyz where y \ne\epsilon, \left| xy \right|> n and x{y}^{i}z \in L for all i \ge 0.From there I don't know where to go.

Thanks!

 

[Evgeny.Makarov]

Please enclose your LaTeX code in \$...\$ or [math]...[/math] tags. Also, you can use [img]URL[/img] to insert images, or you can upload them from your computer. The "Insert Image" button in the second row of the toolbar opens a dialog asking you for a URL or a file name.

The idea is that if a language $L$ is regular, then the set $\{|w|:w\in L\}$ contains an arithmetic progression. (This fact is weaker than the pumping lemma.) This is because $xy^iz\in L$ for all $i$ and $|xy^iz|=|xz|+i|y|$. You need to show that $\{2^n:n\in\Bbb N\}$ does not contain an arithmetic progression because the distance between neighboring elements increases.

 

[JamesBwoii]

I'm still a bit confused. I think the bit I can't do is picking the string to pump with and then put it equal to xyz.

I guess what I am asking is how do I know what string to use?

 

[Evgeny.Makarov]

I guess what I am asking is how do I know what string to use?

The pumping lemma says that if a language is regular, then there exists a number $p$ (pumping length) and all words in the language longer than $p$ can be broken in such a way that some property holds. To prove that a language is not regular, you show that the conclusion is false. That is, you show that for every number $p$ there exists a word in the language longer than $p$ that cannot be broken to satisfy the property.

In this case, it does not really matter which word to choose as long as it is longer than $p$ and is in the language (these properties are required to refute the conclusion). No word of the form $a^{2^n}$ can be represented as $xyz$ in such a way that $xy^iz\in L$ for all $i$. Otherwise, for each $i$ the number $|xz|+i|y|$ would equal $2^k$ for some $k$, which is impossible.

By the way, there is a typo in your statement of the pumping lemma in post #1.

I know for a language to be regular there exists an integer $n > 0$ such that any word $\in L$ with $\left| w \right| > n$ can be represented as $w = xyz$ where $y \ne\epsilon$, $\left| xy \right|> n$ and $x{y}^{i}z \in L$ for all $i \ge 0$.

It should say $\left| xy \right|\le n$, not $\left| xy \right|> n$.

You may find https://driven2services.com/staging/mh/index.php?threads/8355/ useful. It is a about context-free, rather than regular, languages, but the logic of the pumping lemma is the same.

 

[JamesBwoii]

I've read through the link and your post and I think I'm getting there. However, I don't fully understand what you've done here.

No word of the form $a^{2^n}$ can be represented as $xyz$ in such a way that $xy^iz\in L$ for all $i$. Otherwise, for each $i$ the number $|xz|+i|y|$ would equal $2^k$ for some $k$, which is impossible.

I understand the first sentence, but I don't know how you've worked out the bottom bit. I don't get how $xy^iz\in L$ has become $|xz|+i|y|$. How was the $i$ moved from the $y^i$ to $i|y|$. Also where has K come from?

Thanks as always!

 

[Evgeny.Makarov]

No word of the form $a^{2^n}$ can be represented as $xyz$ in such a way that $xy^iz\in L$ for all $i$. Otherwise, for each $i$ the number $|xz|+i|y|$ would equal $2^k$ for some $k$, which is impossible.

I understand the first sentence, but I don't know how you've worked out the bottom bit. I don't get how $xy^iz\in L$ has become $|xz|+i|y|$. How was the $i$ moved from the $y^i$ to $i|y|$. Also where has K come from?

Let's recall the notations used in this thread.

• $L=\{a^{2^n}:n\in\Bbb N\}$.
• $y^i$ denotes the concatenation of $i$ copies of $y$, in particular,
• $a^{2^n}$ is a word consisting of $2^n$ symbols $a$.
• $|w|$ is the length of $w$.

Thus, for all $w\in\{a\}^*$ we have $w\in L\iff |w|=2^k$ for some $k$. Also, $|xy^iz|=|x|+|y^i|+|z|=(|x|+|z|)+i|y|=|xz|+i|y|$.