# Example in page 193 2nd eddition

Posted by giggs
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Example in page 193 2nd eddition July 18, 2007 02:04PM Registered: 13 years ago Posts: 88 Rating: 0
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 Rating: 0
I would like to shed some light, even though I'm no light bringer

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 Registered: 13 years ago Posts: 88 Rating: 0
Thanks 4 the reply, but whats "Einstein wig" ?
 Anonymous User Re: Example in page 193 2nd eddition July 19, 2007 10:04AM Rating: 0
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 Registered: 13 years ago Posts: 88 Rating: 0
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 Rating: 0
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". 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.