REGULAR LANGUAGES AND REGULAR GRAMMARS
In this chapter, we explore two alternative methods for describing regular languages: regular expressions and regular grammars.
Regular expressions, whose form is reminiscent of the familiar arithmetic expressions, are convenient in some applications because of their simple string form, but they are restricted and have no obvious extension to the more complicated languages we will encounter later. Regular grammars, on the other hand, are just a special case of many different types of grammars.
The purpose of this chapter is to explore the essential equivalence of these three modes of describing regular languages. The constructions that make conversion from one form to another are ...