needhelp83
Oct6-08, 12:00 PM
Problem:
Consider the languages over the alphabet \sum = {a,b} defined by L_1 = {a^{k}w|k 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
L_2 = {a^{k}w|k 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 xy^{i}z is not in the language specific for i.
ATTEMPTED SOLUTION:
Assume L_1 is a regular language. If s=a^pba^p and x=a^p, y=ba^p, and z=\epsilon . Using the pumping down method, pump y to i=0. This gives a^p which returns a greater amount of a's in x. This is a contradiction, thus L_1 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!
1. The problem statement, all variables and given/known data
2. Relevant equations
3. The attempt at a solution
Consider the languages over the alphabet \sum = {a,b} defined by L_1 = {a^{k}w|k 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
L_2 = {a^{k}w|k 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 xy^{i}z is not in the language specific for i.
ATTEMPTED SOLUTION:
Assume L_1 is a regular language. If s=a^pba^p and x=a^p, y=ba^p, and z=\epsilon . Using the pumping down method, pump y to i=0. This gives a^p which returns a greater amount of a's in x. This is a contradiction, thus L_1 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!
1. The problem statement, all variables and given/known data
2. Relevant equations
3. The attempt at a solution