Week 12

In week 12, we started a topic called pumping lemma. It is meant to testify that "Not all languages are normal". It is defined by: x which is the string belongs to normal language L, a integer length p which limits the length of x to be at least as long as p(|x| >= p). Then we cut x into three pieces --- u, v and w. The length of the first two element u and v is limited to |uv| <= p. v can not be a empty string. So if we pump up v by k times, for all integer k we should still have u(v^k)w \in L. This theory fails sometime, so we that proves not all language are normal.

After that we started a quite interesting example that has something to do with the recipe, I never thought recipe could actually has relationship with the computer science! Through the process of "making an sandwich" we learnt what is context-free grammars. Like the FSAs we have whole bunch of symbols. V denotes a set of variables, \Sigma indicates a set of terminals which means it would be the end of the "recipe" no further extension is allowed. Like the FSAs it has the starting point which is S.