I recently had an assignment where I have to decide if the languages are regular or not with pumping lemma.
L1 = {xy ∈ {a, b}∗ : |x| = |y|, either x begins with an a and y ends with a b, or neither x nor y is a string of all a's}.
L2 = {xy ∈ {a, b}∗ : |x| = |y|, and x contains the substring aa and y begins with a b}.
For both languages assuming pumping length is n, I provided string s = (a^n)(b^n) since it satisfies "|x| = |y|, x begins with an a and y ends with a b" condition of L1 and "|x| = |y|, x contains the substring aa and y begins with a b" condition of L2. So, s = x(y^i)z, I picked x = (a^n-1), y = a, z = b^n. For any i that is even, total letter count is odd in the x(y^i)z such that s is not in L1 and L2 because |x| cannot be equal to |y| anymore. I am just wondering if I am doing it right or am I missing something?
For L1, let w = a^pbba^p. Then w is in L1 because it can be divided into substrings x = a^pb and y = ba^p of the same length, neither of which is a string of only a. By the pumping lemma for regular languages, w = uvx where |uv| <= p, |v| > 0 and uv^kx is in L1 for all natural numbers k >= 0. However, uv must be a string of a from the beginning of the string; pumping up will cause x, the first half of the resulting string, to consist only of a (assuming the string remains a string of even length; otherwise, the string can't be in L1 anyway); pumping down will cause y, the second half of the resulting string, to consist only of a. Either way, the resulting string is not in the language. This means that L1 cannot be regular.
For L2, let w = a^paba^p. Pumping up means the resulting string will start with a (or have odd length), and so does pumping down. In the former case, the resulting string's y will begin with an a from the first half of w; in the latter, the resulting string's y will begin with a from the second half of w. In any case we get a string not in the language so L2 is not regular either.