Hello!!!

I hope someone can help me at the following exercise:

Show that the following languages are not regular:

a) {ww^R: w ε {a,b}*} (where w^R the word w,written backwards)

b){ww: w ε {a,b}*}

using the following sentence:

->If the language L(A) of an automaton A has an infinite number of words,then there are a,m,t ε Σ*,so that |at|<=| Σk| ( Σk:set of the states),and each word am^(i)t,i>=0,belongs to L(A).

Do you have an idea how to solve the exercise?

## Regular Languages

**Moderators:** phlip, Moderators General, Prelates

### Re: Regular Languages

evinda wrote:->If the language L(A) of an automaton A has an infinite number of words,then there are a,m,t ε Σ*,so that |at|<=| Σk| ( Σk:set of the states),and each word am^(i)t,i>=0,belongs to L(A).

This is known as the pumping lemma.

she/they

gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.

### Re: Regular Languages

Sizik wrote:evinda wrote:->If the language L(A) of an automaton A has an infinite number of words,then there are a,m,t ε Σ*,so that |at|<=| Σk| ( Σk:set of the states),and each word am^(i)t,i>=0,belongs to L(A).

This is known as the pumping lemma.

Could you tell me how to apply this at the exercise,because I am not familiar with such type of exercises?

### Re: Regular Languages

You basically have to show that there is a string xyz (amt using your notation) that is in the language, but at least one of the xy

^{i}z is not in the language. Since the pumping lemma is true for all regular languages, the language is therefore not regular.she/they

gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.

### Re: Regular Languages

Sizik wrote:You basically have to show that there is a string xyz (amt using your notation) that is in the language, but at least one of the xy^{i}z is not in the language. Since the pumping lemma is true for all regular languages, the language is therefore not regular.

Could you explain me further how to do this?

- chridd
- Has a vermicelli title
**Posts:**846**Joined:**Tue Aug 19, 2008 10:07 am UTC**Location:**...Earth, I guess?-
**Contact:**

### Re: Regular Languages

Actually, that's not quite the pumping lemma (though it appears to be a true statement). The pumping lemma says that all strings above a certain length can be split up that way, whereas that statement only says that there's some string that can be split up that way. Unfortunately, there are strings in both the languages that you gave that can be split up that way, making this statement not very useful. Are you sure you wrote down the statement correctly?Sizik wrote:evinda wrote:->If the language L(A) of an automaton A has an infinite number of words,then there are a,m,t ε Σ*,so that |at|<=| Σk| ( Σk:set of the states),and each word am^(i)t,i>=0,belongs to L(A).

This is known as the pumping lemma.

~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores

mittfh wrote:I wish this post was very quotable...

### Re: Regular Languages

chridd wrote:Actually, that's not quite the pumping lemma (though it appears to be a true statement). The pumping lemma says that all strings above a certain length can be split up that way, whereas that statement only says that there's some string that can be split up that way. Unfortunately, there are strings in both the languages that you gave that can be split up that way, making this statement not very useful. Are you sure you wrote down the statement correctly?Sizik wrote:

This is known as the pumping lemma.

Yes,I wrote it down correctly!So,you mean that I can't apply this statement??Is there an other way I could show that the languages above are not regular?

- chridd
- Has a vermicelli title
**Posts:**846**Joined:**Tue Aug 19, 2008 10:07 am UTC**Location:**...Earth, I guess?-
**Contact:**

### Re: Regular Languages

The correct version of the pumping lemma (as explained in the link above) should work.evinda wrote:chridd wrote:Actually, that's not quite the pumping lemma (though it appears to be a true statement). The pumping lemma says that all strings above a certain length can be split up that way, whereas that statement only says that there's some string that can be split up that way. Unfortunately, there are strings in both the languages that you gave that can be split up that way, making this statement not very useful. Are you sure you wrote down the statement correctly?

This is known as the pumping lemma.

Yes,I wrote it down correctly!So,you mean that I can't apply this statement??Is there an other way I could show that the languages above are not regular?

~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores

mittfh wrote:I wish this post was very quotable...

- phlip
- Restorer of Worlds
**Posts:**7573**Joined:**Sat Sep 23, 2006 3:56 am UTC**Location:**Australia-
**Contact:**

### Re: Regular Languages

The regular pumping lemma, in full:

For each regular language "L", there is a length "n", such that all strings in L of length at least n can be broken up into xyz (y not empty, |xy| <= n) such that xy

Or, taking it backwards to get the contrapositive:

For a given language "L", if, for any length "n" you can find some string of length at least n that there doesn't exist any decomposition into xyz (y not empty, |xy| <= n) such that xy

Note that it can only be used in this direction - if a language is regular, it is pumpable; if it is not pumpable, it is not regular. You can't say "this language is pumpable, therefore it is regular" (or "this language is not regular, therefore it is not pumpable") as the inference does not hold in that direction.

The simplest way to use this is a constructive proof. Take your language, and write instructions that say "given any length 'n', I can follow these instructions and get a string in the language that's longer than n, but which can't be pumped, and here is the proof it can't be pumped". If you can do that, then the language can't be regular.

For each regular language "L", there is a length "n", such that all strings in L of length at least n can be broken up into xyz (y not empty, |xy| <= n) such that xy

^{i}z is in L for all i >= 0.Or, taking it backwards to get the contrapositive:

For a given language "L", if, for any length "n" you can find some string of length at least n that there doesn't exist any decomposition into xyz (y not empty, |xy| <= n) such that xy

^{i}z is in L for all i>=0... then L must be not regular.Note that it can only be used in this direction - if a language is regular, it is pumpable; if it is not pumpable, it is not regular. You can't say "this language is pumpable, therefore it is regular" (or "this language is not regular, therefore it is not pumpable") as the inference does not hold in that direction.

The simplest way to use this is a constructive proof. Take your language, and write instructions that say "given any length 'n', I can follow these instructions and get a string in the language that's longer than n, but which can't be pumped, and here is the proof it can't be pumped". If you can do that, then the language can't be regular.

Code: Select all

`enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};`

void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}

### Who is online

Users browsing this forum: No registered users and 8 guests