TR02-06 (2002) – Transforming Self-Embedded Context-Free Grammars into Regular Expressions

St.Andrei, S.Cavadini, W-N. Chin

Our paper refers to the context-free and regular languages. Wepoint out in an algorithmic manner using system of equationsthe situations when a context-free grammar generates a regularlanguage: the case of one-letter alphabet and some cases ofself-embedded context-free grammars.Moreover, we describe some other sufficient conditions when aself-embedded context-free grammar generates a (non)regularlanguage. The paper proves that the systems of equations withself-embeddedness terms like XaX still have as solution a regularlanguage. In order to enlarge the class of context-free grammarswhich generates regular languages, the class of one-letterfactorizable context-free grammars is introduced.

Parts of this technical report have been published as follows:

1. Andrei, St., Cavadini, S.C., Chin, W.N.: A New Algorithmfor Regularizing One-Letter Context-Free Grammars. Theoretical Computer Science, Volume 306, Issues 1-3, pp. 113-122 (2003)

2. Andrei, St., Chin, W.N., Cavadini, S.C.: Self-embedded context-freegrammars with regular counterparts. Acta Informatica, Volume 40, Number 5, pp. 349-365 (2004)

Bibtex

@TechReport{tscgre,
  author = 	 { S. Andrei and  S. Cavadini and W-N. Chin},
  title = 	 {Transforming Self-Embedded Context-Free Grammars into Regular Expressions},
  institution =  {University ``A.I.Cuza'' of Iac{s}i, Faculty of
Computer Science},
  year = 	 {2002},
  number = 	 {TR 02-06},
  note = 	 {URL:http://www.infoiasi.ro/~tr/tr.pl.cgi}
}