Generating All Permutations by Context-Free Grammars in Greibach Normal Form

P.R.J. Asveld

Research output: Book/ReportReportProfessional

42 Downloads (Pure)

Abstract

We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). 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 $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.
Original languageUndefined
Place of PublicationEnschede
PublisherHuman Media Interaction (HMI)
Number of pages22
Publication statusPublished - 2007

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
No.FS-07-05/TR-CTIT-07-83
ISSN (Print)1381-3625

Keywords

  • METIS-245784
  • EWI-11418
  • HMI-SLT: Speech and Language Technology
  • IR-64468

Cite this

Asveld, P. R. J. (2007). Generating All Permutations by Context-Free Grammars in Greibach Normal Form. (CTIT Technical Report Series; No. FS-07-05/TR-CTIT-07-83). Enschede: Human Media Interaction (HMI).
Asveld, P.R.J. / Generating All Permutations by Context-Free Grammars in Greibach Normal Form. Enschede : Human Media Interaction (HMI), 2007. 22 p. (CTIT Technical Report Series; FS-07-05/TR-CTIT-07-83).
@book{5b6305d6c32b4c578f0a24908e44194b,
title = "Generating All Permutations by Context-Free Grammars in Greibach Normal Form",
abstract = "We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). 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 $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.",
keywords = "METIS-245784, EWI-11418, HMI-SLT: Speech and Language Technology, IR-64468",
author = "P.R.J. Asveld",
year = "2007",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Human Media Interaction (HMI)",
number = "FS-07-05/TR-CTIT-07-83",

}

Asveld, PRJ 2007, Generating All Permutations by Context-Free Grammars in Greibach Normal Form. CTIT Technical Report Series, no. FS-07-05/TR-CTIT-07-83, Human Media Interaction (HMI), Enschede.

Generating All Permutations by Context-Free Grammars in Greibach Normal Form. / Asveld, P.R.J.

Enschede : Human Media Interaction (HMI), 2007. 22 p. (CTIT Technical Report Series; No. FS-07-05/TR-CTIT-07-83).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Generating All Permutations by Context-Free Grammars in Greibach Normal Form

AU - Asveld, P.R.J.

PY - 2007

Y1 - 2007

N2 - We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). 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 $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.

AB - We consider context-free grammars $G_n$ in Greibach normal form and, particularly, in Greibach $m$-form ($m=1,2$) which generates the finite language $L_n$ of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). 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 $G_n$ as functions of $n$. As in the case of Chomsky normal form these descriptional complexity measures grow faster than any polynomial function.

KW - METIS-245784

KW - EWI-11418

KW - HMI-SLT: Speech and Language Technology

KW - IR-64468

M3 - Report

T3 - CTIT Technical Report Series

BT - Generating All Permutations by Context-Free Grammars in Greibach Normal Form

PB - Human Media Interaction (HMI)

CY - Enschede

ER -

Asveld PRJ. Generating All Permutations by Context-Free Grammars in Greibach Normal Form. Enschede: Human Media Interaction (HMI), 2007. 22 p. (CTIT Technical Report Series; FS-07-05/TR-CTIT-07-83).