Back to University of Twente portal
From left-regular to Greibach normal form grammars
Nijholt, A. (1979) From left-regular to Greibach normal form grammars. Information Processing Letters, 9 (1). pp. 51-55. ISSN 0020-0190
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 628Kb |
| Abstract: | Each context-free grammar can be transformed to a context-free grammar in Greibach normal form, that is, a context-free grammar where each right-hand side of a prorfuction begins with a terminal symbol and the remainder of the right-hand side consists of nonterminal symbols. In this short paper we show that for a left-regular grammar G we can obtain a right-regular grammar G’ (which is by definition in Greibach normal form) which left-to-right 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 context-free grammar G” in Greibach normal form which right covers the left-regular 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/0020-0190(79)90109-1 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page