Abstract
Strongly Regular Grammars and Regular Approximation of Context-Free Languages
by: Omer Egecioglu
Abstract:
We consider algorithms for approximating context-free grammars by regular grammars, making use of Chomsky's characterization of non-self-embedding grammars as generating regular languages and a transformation by Mohri and Nederhof on sets of mutually recursive nonterminals. We give an exposition of strongly regular grammars and this transformation, and use it as a subprocedure to obtain tighter regular approximations to a given context-free grammar. In another direction, the generalization by a 1-lookahead extends Mohri and Nederhof's transformation by incorporating more context into the regular approximation at the expense of a larger grammar.
Keywords:
Context-free grammar, strongly regular grammar, non-self-embedding grammar, regular language, regular approximation.
Date:
April 2009
Document: 2009-06
