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?
What we have already done this semester:
Definition: DFA represents regular language
Theorem: NFA \(\Longleftrightarrow\) DFA
Theorem: RegEx \(\Longleftrightarrow\) NFA
What we will do next:
Theorem: DFA \(\Longleftrightarrow\) regular grammar
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.
