From leftregular to Greibach normal form grammars
Nijholt, A. (1979) From leftregular to Greibach normal form grammars. Information Processing Letters, 9 (1). pp. 5155. ISSN 00200190

PDF
643kB 
Abstract:  Each contextfree grammar can be transformed to a contextfree grammar in Greibach normal form, that is, a contextfree grammar where each righthand side of a prorfuction begins with a terminal symbol and the remainder of the righthand side consists of nonterminal symbols. In this short paper we show that for a leftregular grammar G we can obtain a rightregular grammar G’ (which is by definition in Greibach normal form) which lefttoright covers G (in this case left parses of G’ can be mapped by a homomorphism on right parses of G. Moreover, it is possible to obtain a contextfree grammar G” in Greibach normal form which right covers the leftregular grammar G (in this case right parses of G” are mapped on right parses of G). 
Item Type:  Article 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/66922 
Official URL:  http://dx.doi.org/10.1016/00200190(79)901091 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page