4. (15 points) Let's say you are playing a sequences of matches of chess with an opponent. You are keeping track of how many times you win and lose. You are very stubborn and you will keep playing games until you have more wins than losses at which point you will stop playing and declare yourself better than the other player. Consider the following language L over the alphabet S = {0,1} that consists of all possible strings of 0 and 1 that could result in the sequence described above where a 0 counts as a loss and a 1 counts as a win. For example: 1 L because you could win in your first game and stop there. 0001111 E L because you could lose the first 3 games and win the last 4 at which point you will stop. 0101011 E L because you will lose and win back and forth until you win twice in a row at which point you will stop. 010010111 L you get the idea. 1111000 L because you would have already stopped after the first win. (a) Draw the state diagram of a PDA that recognizes this language. (b) Use pumping lemma to prove this language is not regular