Application of finite graph models of context fue languages.

Abstract

A finite graph model for a context?free language is proposed. The model is called an extended transition system; its nodes encode [pushdown automata state, top stack symbol] pairs and its arcs encode pushdown automaton transitions. Three applications of this model are presented. Graph theoretic proofs of the Pumping Lemma, Parikh's theorem and the Chomsky–Schützenberger theorem are given. A new regularity test for deterministic context?free languages is given which has complexity O(qt)4O(q t)^4O(qt)4 where qqq is the number of states and ttt the number of stack symbols of the deterministic pushdown automaton for the language. A new algorithm for the near minimal cost correction of substitution errors in deterministic context?free languages is presented. This algorithm has time complexity O(n)O(n)O(n) for a subclass of the deterministic context?free language.