Speed of Recognition of Context-Free Languages by Array Automata
S. Rao Kosaraju · SIAM Journal on Computing · 1975
The recognition speed of context-free languages (CFL’s) using arrays of finite state machines is considered. It is shown that CFL’s can be recognized by 2-dimensional arrays in linear time and by 1-dimensional arrays in time $n^2 $.