Date: Wed, 08 Jan 1997 20:52:36 GMT Server: NCSA/1.4.2 Content-type: text/html
For the purposes of this construction we use regular grammars
which have productions of the form and
.
To generate the the empty language no productions are needed.
To generate the singleton language
just use the two
productions
and
.
For the recursive part of the construction,
let and
be regular
grammars which generate the languages defined by the regular
expression
and
, respectively. We will assume
that
. Given the regular
expression
which is built from the regular expressions
and
we define a new regular grammar
which
generates the language defined by
.
There are three cases to consider:
Case 1. . Let
be a new
non-terminal.
Case 2. .
Case 3. . Let
be a new
non-terminal.