MHB Proving languages are not regular.

  • Thread starter Thread starter JamesBwoii
  • Start date Start date
  • Tags Tags
    Regular
JamesBwoii
Messages
71
Reaction score
0
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!
 
Physics news on Phys.org
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.
 
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?
 
JaAnTr said:
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.
JaAnTr said:
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.
 
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.
Evgeny.Makarov said:
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 said:
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.

JaAnTr said:
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|$.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Replies
3
Views
2K
Replies
18
Views
3K
Replies
1
Views
2K
Replies
24
Views
4K
Replies
3
Views
2K
Replies
1
Views
2K
Replies
17
Views
4K
Back
Top