Generating All Permutations by ContextFree Grammars in Greibach Normal Form
Asveld, P.R.J. (2007) Generating All Permutations by ContextFree Grammars in Greibach Normal Form. [Report]

PDF
216kB 
Abstract:  We consider contextfree grammars in Greibach normal form and, particularly, in Greibach form () which generates the finite language of all strings that are permutations of different symbols (). These grammars are investigated with respect to their descriptional complexity, i.e., we determine the number of nonterminal symbols and the number of production rules of as functions of . As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function. 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Link to this item:  http://purl.utwente.nl/publications/64468 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 245784