4.4. Regular Grammars¶
4.4.1. Introduction to Regular Grammars¶
Regular grammars are another way to describe regular languages. Recall that a grammar is made of of terminals, variables, and production rule. As the name implies, a regular grammar is a special type of grammar (we will see plenty of grammars later that are not regular). Which begs the question: What makes a grammar regular?
Of course, this will mean that DFAs, NFAs, REs, regular languages, and regular grammars all have exactly the same power. By this, we mean that DFAs, NFAs, Regular Expressions, and Regular Grammars all can recognize, or if you perfer they can all represent, exactly the same set of languages: the regular languages.
4.4.4. Converting between Left-linear and Right-linear Grammars¶
4.4.5. Summary¶
In this module we introduced regular grammars, defined to be either left-regular or right-regular grammars. We confirmed that we can convert between left- and right-regular grammars are really equivalent (by showing how to convert between them). We showed that NFAs can be converted to/from regular grammars, which means that regular grammars have the same power as our other representations for regular languages.
