- #1
needhelp83
- 199
- 0
Problem:
Consider the languages over the alphabet [tex]\sum = {a,b}[/tex] defined by [tex] L_1 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is greater than or equal to k},
and
[tex] L_2 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is less than or equal to k},
For language, use pumping lemma to prove that the language is not regular. For each proof, you must state s in terms of the integer p from the pumping lemma, and then explain clearly why some [tex]xy^{i}z[/tex] is not in the language specific for i.
ATTEMPTED SOLUTION:
Assume [tex]L_1[/tex] is a regular language. If [tex] s=a^pba^p [/tex] and [tex]x=a^p, y=ba^p, and z=\epsilon [/tex]. Using the pumping down method, pump y to i=0. This gives [tex] a^p[/tex] which returns a greater amount of a's in x. This is a contradiction, thus [tex] L_1 [/tex] is not a regular language.
I don't believe this is right. I am really struggling with this pumping and looking for any help I can get. Thanks!
Consider the languages over the alphabet [tex]\sum = {a,b}[/tex] defined by [tex] L_1 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is greater than or equal to k},
and
[tex] L_2 = {a^{k}w|k [/tex] is the number of consecutive a's at start, w is the rest of the string, and the number of a's in w is less than or equal to k},
For language, use pumping lemma to prove that the language is not regular. For each proof, you must state s in terms of the integer p from the pumping lemma, and then explain clearly why some [tex]xy^{i}z[/tex] is not in the language specific for i.
ATTEMPTED SOLUTION:
Assume [tex]L_1[/tex] is a regular language. If [tex] s=a^pba^p [/tex] and [tex]x=a^p, y=ba^p, and z=\epsilon [/tex]. Using the pumping down method, pump y to i=0. This gives [tex] a^p[/tex] which returns a greater amount of a's in x. This is a contradiction, thus [tex] L_1 [/tex] is not a regular language.
I don't believe this is right. I am really struggling with this pumping and looking for any help I can get. Thanks!