# Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form

P.R.J. Asveld

Research output: Book/ReportReportProfessional

5 Citations (Scopus)

For each alphabet $\Sigma_n=\{a_1,a_2,\ldots,a_n\}$, linearly ordered by $a_1<a_2<\cdots<a_n$, let $C_n$ be the language of circular or cyclic shifts over $\Sigma_n$, i.e., $C_n=\{a_1a_2\cdots a_{n-1}a_n,$$a_2a_3\cdots a_na_1,\ldots,a_na_1\cdots a_{n-2}a_{n-1}\}. We study a few families of context-free grammars G_n (n\geq1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals \nu(n), the number of rules \pi(n) and the number of leftmost derivations \delta(n) of G_n. As in the case of Chomsky normal form, these \nu, \pi and \delta are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal with respect to all these measures remains open. Original language Undefined Enschede Centrum voor Telematica en Informatie Technologie 12 Published - 2007 ### Publication series Name CTIT Technical Report Series 07-28 1381-3625 ### Keywords • HMI-SLT: Speech and Language Technology • IR-67078 • METIS-245697 • EWI-9722 ### Cite this Asveld, P. R. J. (2007). Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. (CTIT Technical Report Series; No. 07-28). Enschede: Centrum voor Telematica en Informatie Technologie. Asveld, P.R.J. / Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. Enschede : Centrum voor Telematica en Informatie Technologie, 2007. 12 p. (CTIT Technical Report Series; 07-28). @book{a12539048dc34025aac87b230c849dfd, title = "Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form", abstract = "For each alphabet \Sigma_n=\{a_1,a_2,\ldots,a_n\}, linearly ordered by a_1<a_2<\cdots<a_n, let C_n be the language of circular or cyclic shifts over \Sigma_n, i.e., C_n=\{a_1a_2\cdots a_{n-1}a_n,$$a_2a_3\cdots a_na_1,\ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We study a few families of context-free grammars $G_n$ ($n\geq1$) in Greibach normal form such that $G_n$ generates $C_n$. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals $\nu(n)$, the number of rules $\pi(n)$ and the number of leftmost derivations $\delta(n)$ of $G_n$. As in the case of Chomsky normal form, these $\nu$, $\pi$ and $\delta$ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal with respect to all these measures remains open.",
keywords = "HMI-SLT: Speech and Language Technology, IR-67078, METIS-245697, EWI-9722",
author = "P.R.J. Asveld",
year = "2007",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centrum voor Telematica en Informatie Technologie",
number = "07-28",

}

Asveld, PRJ 2007, Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. CTIT Technical Report Series, no. 07-28, Centrum voor Telematica en Informatie Technologie, Enschede.
Enschede : Centrum voor Telematica en Informatie Technologie, 2007. 12 p. (CTIT Technical Report Series; No. 07-28).

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - Asveld, P.R.J.

PY - 2007

Y1 - 2007

N2 - For each alphabet $\Sigma_n=\{a_1,a_2,\ldots,a_n\}$, linearly ordered by $a_1<a_2<\cdots<a_n$, let $C_n$ be the language of circular or cyclic shifts over $\Sigma_n$, i.e., $C_n=\{a_1a_2\cdots a_{n-1}a_n,$$a_2a_3\cdots a_na_1,\ldots,a_na_1\cdots a_{n-2}a_{n-1}\}. We study a few families of context-free grammars G_n (n\geq1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals \nu(n), the number of rules \pi(n) and the number of leftmost derivations \delta(n) of G_n. As in the case of Chomsky normal form, these \nu, \pi and \delta are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal with respect to all these measures remains open. AB - For each alphabet \Sigma_n=\{a_1,a_2,\ldots,a_n\}, linearly ordered by a_1<a_2<\cdots<a_n, let C_n be the language of circular or cyclic shifts over \Sigma_n, i.e., C_n=\{a_1a_2\cdots a_{n-1}a_n,$$a_2a_3\cdots a_na_1,\ldots,a_na_1\cdots a_{n-2}a_{n-1}\}$. We study a few families of context-free grammars $G_n$ ($n\geq1$) in Greibach normal form such that $G_n$ generates $C_n$. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals $\nu(n)$, the number of rules $\pi(n)$ and the number of leftmost derivations $\delta(n)$ of $G_n$. As in the case of Chomsky normal form, these $\nu$, $\pi$ and $\delta$ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal with respect to all these measures remains open.

KW - HMI-SLT: Speech and Language Technology

KW - IR-67078

KW - METIS-245697

KW - EWI-9722

M3 - Report

T3 - CTIT Technical Report Series

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

PB - Centrum voor Telematica en Informatie Technologie

CY - Enschede

ER -

Asveld PRJ. Generating All Circular Shifts by Context-Free Grammars in Greibach Normal Form. Enschede: Centrum voor Telematica en Informatie Technologie, 2007. 12 p. (CTIT Technical Report Series; 07-28).