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?

1 / 18 Settings

<<<>>>

Regular Grammars are another way to define a regular language.

Saving...
Server Error
Resubmit

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.2. Converting Regular Grammars to NFAs¶

1 / 15 Settings

<<<>>>

We want to prove that for any regular language, there is a regular grammar that describes it. We will use our standard approach of proving two representations are equivalent by constructing a way to convert between them. So, we prove the following two conversions:
1 - For any right-linear grammar there is an equivalent NFA. This will mean that regular grammars don't accept more than regular languages.
2 - For any NFA, there is a right-linear grammar. This will mean that all regular languages can be represented by a regular grammar.

1. S
2. →
3. aB

1. S
2. →
3. aA

1. A
2. →
3. aA

1. A
2. →
3. bS

1. A
2. →
3. bB

1. B
2. →
3. bS

1. B
2. →
3. λ

2. →

A

B

S

a

a

a

b

b

b

D

a

b

Saving...
Server Error
Resubmit

4.3.3. Converting NFAs to Regular Grammars¶

1 / 14 Settings

<<<>>>

Our second step in proving that regular grammars represent exactly the set of regular languages is to show that we can convert any NFA to a regular grammar. In particular, we will convert to a right-linear grammar.

Q0

Q1

b

a

a

2. →

2. →

2. →

2. →

2. →

Saving...
Server Error
Resubmit

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.