Ok, I know that this isn't a programming question but it is a computing question so it is relevant.
Basically, how can I use the pumping lemma to prove that this language is not regular?
{w in {0,1}* | if the length of w is odd then the middle symbol is 0}
Please answer this as simple as possible as whilst I know about models of computation, I am relatively new to it.
Thank you very much in advance!
According to the pumping lemma, if that language is regular then there must exist a number p such that for all strings longer than p in the language, we can decompose that string into x + y + z, where each of x, y, and z are strings and |y| >= 1, |x + y| <= p, and x + (y * i) + z is in the language for all non-negative integers i.
Now observe that for every non-negative integer i, the string "1" * i + "0" + "1" * i is in the language. (That is, the string of i 1s followed by a single 0 and then i more 1s)
Specifically, the string S consisting of p 1s followed by a 0 and then p more 1s is in the language. Since this string has length 2 p + 1, this string is long enough that it can be broken into three strings x, y, and z as in the pumping lemma. Since |x + y| <= p, it must be that x and y are all 1s, and the only 0 character in S is in z. Now consider the string S' = x + y + y + y + z. Since we added 2*|y| characters to it, S' must also have an odd length. But we added some number of 1 characters to the left of the only 0 in S, and didn't add any 1 characters to the right of the 0. So S' doesn't have a 0 as its middle character, and therefore S' isn't in the language.
Therefore, we've shown that the language can't be pumped as the pumping lemma requires. Therefore, the language is not regular.
