pumping lemma for context free languages

use the pumping lemma to show that the language is not context free.
we assume that is a CFL and obtain a contradiction. let be the pumping length for that is guaranteed to exist by the pumping lemma. select the string . clearly is a member of and of length at least . the pumping lemma states that can be pumped, but we show that it cannot. in other words, we show that no matter how we divide into , one of the three conditions of the lemma is violated. first, condition 2 stipulates that either or is nonempty. then we consider one of two cases, depending on whether substrings and contain more than one type of alphabet symbol.

1. when both and contain only one type of alphabet symbol, does not contain both ’s and ’s or both ’s and ’s, and the same holds for . in this case, the string cannot contain equal numbers of 's, 's, and 's. therefore, it cannot be a member of . that violates condition 1 of the lemma and is thus a contradiction.
2. when either or contains more than one type of symbol, may contain equal numbers of the three alphabet symbols but not in the correct order. hence it cannot be a member of and a contradiction occurs.

one of these cases must occur. because both cases result in a contradiction, a contradiction is unavoidable. so the assumption that is a CFL must be false.
thus we have proved that B is not a CFL.
[cite:;from @sipser_comp_2012 example 2.36]

let . use the pumping lemma to show that is not a cfl. assume that is a cfl and obtain a contradiction. let be the pumping length given by the pumping lemma.
this time choosing string is less obvious. one possibility is the string . it is a member of and has length greater than , so it appears to be a good candidate. but this string can be pumped by dividing it as follows, so it is not adequate for our purposes.
let's try another candidate for . intuitively, the string seems to capture more of the "essence" of the language than the previous candidate did. in fact, we can show that this string does work, as follows.
we show that the string cannot be pumped. this time we use condition 3 of the pumping lemma to restrict the way that can be divided. it says that we can pump by dividing , where .
first, we show that the substring must straddle the midpoint of . otherwise, if the substring occurs only in the first half of , pumping up to moves a 1 into the first position of the second half, and so it cannot be of the form . similarly, if occurs in the second half of , pumping up to moves a 0 into the last position of the first half, and so it cannot be of the form .
but if the substring straddles the midpoint of , when we try to pump down to it has the form , where and cannot both be . this string is not of the form . thus cannot be pumped, and is not a CFL.
[cite:;taken from @sipser_comp_2012 example 1.75]

where is , defined by
in the ladder of language hierarchy?
does pertain the pumping property, but it isnt regular, try to find equivalence relations.
it is recognized by the following grammar:

isnt regular, doesnt pertain the pumping lemma
recognized by cfg

recognized by
pertains the pumping lemma, but isnt regular (prove it)