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 |
|
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 
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).
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 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"
. 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.
-------------------------------------------------------
> 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.