Automata Theory

1- ) Assume L is regular, and let p 1 be its pumping length. Define s a 2p b p and let xyz s be a partitioning satisfying | xy | p and | y | 1. Since | xy | p, partition y consist of only as. String xy2 z therefore has 2p` | y | as and p bs. Since | y | 1, then 2p 2p` | y |, string xy2 z R L contradicting the pumping lemma. We conclude that L is not regular.

2- ) Define L1 to be the language of all even-length string. L1 is regular because there is a DFA that accepts it: A pt0, 1u, , , 0, t0uq where tpp0, q, 1q,pp1, q, 0q | P u. For any language L, observe that EpLq L L1. Thus, if L is regular then EpLq is regular by the closure property of intersection.