Search

Your search keyword '"Freidrich, J."' showing total 5 results
Start Over Author "Freidrich, J." Publisher elsevier bv
5 results on '"Freidrich, J."'

5. On greibach normal form construction

Author

Freidrich J. Urbanek

Subjects
Grammar, General Computer Science, Generalization, Greibach normal form, media_common.quotation_subject, Context-free grammar, Theoretical Computer Science, Algebra, Formal language, Rewriting, Algorithm, Mathematics, media_common, Computer Science(all)
Abstract

We present an algorithm which, given an arbitrary e-free and chain-free context-free grammar, produces an equivalent context-free grammar in Greibach normal form (GNF). This algorithm is a generalization of an algorithm recently presented by Ehrenfeucht and Rozenberg. Using this algorithm the well-known GNF construction of Rosenkrantz can be obtained. Furthermore it is possible to rewrite a given context-free grammar by a GNF grammar which has at most twice as much nonterminals as the original grammar. This result is shown to be optimal (with respect to the number of nonterminals).

Published
1985
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results