[comp.theory] CFL Equivalence

litow@csd4.csd.uwm.edu (Bruce E Litow) (11/09/89)

Perhaps it should be pointed out that the case,L(G) = Sigma^*,where
G is an unambiguous context-free grammar is decidable. This is due
to Salomaa and others. The power series <G,x> = Sum_n=0^infty
c_nx^n where c_n = number of length n words in L(G) can be implicitly
defined as a multivariate polynomial equations (as many variables
as nonterminals in G) and <Sigma^*> is explicitly given as
1/(1-kx) where k = Card(Sigma). Thus equivalence is a sentence in
the first order theory of real arithmetic which is a decidable
(Tarski,then many others) theory. Note that the fact that c_n is
correct depends on G being unambiguous. This is discussed in
``Automata Theoretic Aspects of Formal Power Series'' by Salomaa and
Soittola.