next up previous contents
Next: E'beth's presentation continued Up: Properties of Regular Sets Previous: Neil Gershenfeld's digression

Han's explanation of FA limitations

\begin{displaymath}
{0^n 1^n 2^n} = { 012, 001122, 000111222, \ldots } \end{displaymath}

This example breaks regular language, because number of each element is critical. This prevents pumping (no way to construct larger strings using a single repeated substring) , and thus you would need an arbitrarily large FA.

Connection between stacks and CFGs - the addition of the stack to a FA results makes a pushdown automata. The infinite stack allows a the acceptance of a context free languages (such as the example above) by pushdown automatas which cannot be accepted by FAs.



root
6/8/1998