Date: Wed, 08 Jan 1997 20:52:36 GMT Server: NCSA/1.4.2 Content-type: text/html Construction of Regular Grammars from Regular Expressions



next up previous
Next: About this document

Construction of Regular Grammars from Regular Expressions

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.





James Fix
Mon Jan 22 13:09:21 PST 1996