Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!litow
From: litow@csd4.csd.uwm.edu (Bruce E Litow)
Newsgroups: comp.theory
Subject: CFL Equivalence
Message-ID: <851@uwm.edu>
Date: 9 Nov 89 12:51:25 GMT
Sender: news@uwm.edu
Reply-To: litow@csd4.csd.uwm.edu (Bruce E Litow)
Organization: University of Wisconsin-Milwaukee
Lines: 12

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.