Week 12

Main topic of week 12: pumping lemma, context free grammer

Since not all the expressions are regular, ie, string with same number 1s and 0s, so the idea of having pumping lemma is to prove some expression that is regular. The main scheme of pumping lemma is that if you got a DFSA denotes L has p states, then every string has length greater than p can be written as uv^kw where v is not empty. Idea behind this is that somewhere in the string will generate a loop back to some states, since the total string is greater than the total number of states. So we could repeat that cycle K times, and the string uv^kw will still be accepted by L.