4.3. Regular Grammars¶
4.3.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.3.3. Converting NFAs to Regular Grammars¶
Actually, we have only shown that right-linear grammars are equivalent to regular languages. This might leave us with some doubts about the relationship between left-linear and right-linear grammars. However, similar constructions can be used to show the ability to convert to/from left-linear grammars as well.
4.3.4. Something to Think About¶
Consider the language \(L = \{a^nb^n \mid n>0\}\). Is language \(L\) regular? Do you think that you can draw a DFA, regular expression, or Regular grammar for this language? Think about it for a moment—but don’t spend a long time trying.
Consider this grammar: \(G = \{S \rightarrow aSb \mid ab\}\). This is a nice and easy solution to finding a grammar for this language. There is just one problem: This grammar is not regular! We will come back to this question later.
