o so, i tried looking at the example 2.4.2, and got stuck on o the part " y!=e that is, y=a^i for some i>0 " and i don't get o the last sentence that proves its contradiction.The three examples that follow Theorem 2.4.1 are examples of how you might prove that a langauge is not regular. Example 2.4.2 in particular works with a language of the form (a^i)(b^i), or anything with some number of a's (i of them, in particular) followed by the same number of b's. At heart, this is a proof by contradiction.
1) Develop a string, w, that will break the language
Now, according to Theorem 2.4.1, if this is a regular language, there is some number 'n' above which 2d, above, applies. So, let's take this n, whatever it is, and make a string w = (a^n)(b^n) (that is, n a's followed by n b's).
2) Show that the 'y' part of the xyz breakdown of w is of the form a^j, j > 0
By the theorem, we can break 'w' (since it's longer than n characters) down into three parts: x, y, and z. Specifically, xy must be no more than n characters long (see 2c, above). And, since the first n characters are all a's, xy must be all a's as well. Therefore, the 'y' part of xy (which must not be an empty string, see 2b above) has to be some non-zero length string made entirely of a's, which we can represent as (a^j), j > 0.
3) Show that the string xz, which according to the theorem must be in the langauge, is not, indicating that this is not a regular langauge.
Also according to the theorem, if xyz is in the language, then any string of the form x(y^i)z, i>=0, is in the language (see 2d, above). Therefore, if we set i=0, the string xz (or, w with 'y' taken out of the middle)must be in the langauge. In our case, xz is our original string 'w' with (a^i, or some number of a's) taken out of the middle. This new string, xz, is (a^(n-j))(b^n), the same as the original w without a few of the a's. However, this is explicitly not of the form (a^n)(b^n) because j > 0.
Comments:
Part of what made this tricky is that the book used the same dummy variable ('i') to describe the langauge, (a^i)(b^i) and the length of the middle string, y, (a^i). Above, I used 'i' for the former and 'j' for the latter.
Page maintained by Salvatore Domenick Desiano (sal@ri.cmu.edu).
smile.