Regular Languages

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

Regular Languages

Postby evinda » Sun Dec 15, 2013 12:28 am UTC

Hello!!! :D
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?

User avatar
Sizik
Posts: 1261
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Regular Languages

Postby Sizik » Sun Dec 15, 2013 3:50 am UTC

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:
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.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

Re: Regular Languages

Postby evinda » Sun Dec 15, 2013 9:10 am UTC

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? :oops:

User avatar
Sizik
Posts: 1261
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Regular Languages

Postby Sizik » Sun Dec 15, 2013 4:29 pm UTC

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 xyiz 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:
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.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

Re: Regular Languages

Postby evinda » Sun Dec 15, 2013 9:44 pm UTC

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 xyiz 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?

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

Re: Regular Languages

Postby chridd » Mon Dec 16, 2013 1:33 am UTC

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.
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?
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...

evinda
Posts: 32
Joined: Fri May 03, 2013 10:16 pm UTC

Re: Regular Languages

Postby evinda » Mon Dec 16, 2013 7:17 pm UTC

chridd wrote:
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.
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?


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?

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

Re: Regular Languages

Postby chridd » Mon Dec 16, 2013 7:50 pm UTC

evinda wrote:
chridd wrote:
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.
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?


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?
The correct version of the pumping lemma (as explained in the link above) should work.
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
mittfh wrote:I wish this post was very quotable...

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

Re: Regular Languages

Postby phlip » Sun Dec 22, 2013 11:41 pm UTC

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 xyiz 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 xyiz 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)⚠);}
[he/him/his]


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 8 guests