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

Our paper refers to the context-free and regular languages. We point out in an algorithmic manner using system of equations the situations when a context-free grammar generates a regular language: the case of one-letter alphabet and some cases of self-embedded context-free grammars. Moreover, we describe some other sufficient conditions when aself-embedded context-free grammar generates a (non)regular language.

The paper proves that the systems of equations with self-embeddedness terms like XaX still have as solution a regular language. In order to enlarge the class of context-free grammars which generates regular languages, the class of one-letter factorizable 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)

Full Document (PS)

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},
    url = 	{https://publications.info.uaic.ro/technical-reports/archive/tr02-06-2002-transforming-self-embedded-context-free-grammars-into-regular-expressions/}
}