Welcome! Log In Create A New Profile

Advanced

Example in page 193 2nd eddition

Posted by giggs 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Example in page 193 2nd eddition
July 18, 2007 02:04PM
Can anybody please try 2 bring some light on the last example @ the and of the page(193). I do get the 1st Observation, but not the second Observation.
Anonymous User
Re: Example in page 193 2nd eddition
July 18, 2007 07:28PM
I would like to shed some light, even though I'm no light bringer smiling smiley

Firstly, the languages that we use throughout the book so far contain only a's and b's. I think this corresponds nicely with binary in computers. So we are essentially working with binary strings. More specifically, binary strings which will either bring a machine (computer) to a desired or undesired state.

The pumping lemma is used exclusively (I think) to distinguish a regular language or irregular language.

The pumping lemma states (there's a theorem somewhere) that if a language were regular, there would exist 3 strings (or binary combinations) of x, y, z such that xyz and xyyz were both words in this language. (This is verbatim from the bottom of page 193)

Pumping lemmas prove irregular languages (I think) by contradiction. The string is analyzed in the context of the language and the language is then proved regular or irregular.

It is clear from the given string structure that there can exist only one b, slap in the middle of that string. So observation 1 makes sense by intuition.

Observation 2 refers to the lemma. It observes that if the y part of the string (from the abovementioned words allowed in the language by the lemma theorem) were all a's, then the b part of the string (there must be a b, by the definition given of this language) must be either in the x part or the z part.
If this were so *puts on Einstein wig* the string xyyz has increased the number of a's either before or after the b in the string, but not both. This is contrary to the language definition.

*takes off Einstein wig* Then they draw those two conclusions.


Hope this helps (and is correct).
Re: Example in page 193 2nd eddition
July 19, 2007 09:03AM
Thanks 4 the reply, but whats "Einstein wig" ?
Anonymous User
Re: Example in page 193 2nd eddition
July 19, 2007 10:04AM
It's the appearance I take when I make a scientific observation. Ok, it's a little humour. Sorry.
Re: Example in page 193 2nd eddition
July 19, 2007 10:22AM
Rick, how do i choose the values for x,y,z if i have a language like
{b aba aabba ...} ? (same page)
Anonymous User
Re: Example in page 193 2nd eddition
July 19, 2007 10:54AM
giggs Wrote:
-------------------------------------------------------
> Rick, how do i choose the values for x,y,z if i
> have a language like
> {b aba aabba ...} ? (same page)

Surely you mean {b aba aabaa ...} ? There are only 2 languages defined on page 193:
a^n b a^n and a^n b^n (where ^n means "to the power of n"winking smiley. You should not look at x,y,z as variables to fill. They are more like templates to put your language onto. If the language fits the template, then it's regular. If the language doesn't "fit", then it's irregular.

As to how to fit the language, please re-read my first post.

Good luck.
Sorry, only registered users may post in this forum.

Click here to login