35.6.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.

35.6.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

35.6.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

35.6.4. Converting between Left-linear and Right-linear Grammars¶

1 / 27 Settings

<<<>>>

Previously, we saw how to convert an NFA to a right-regular grammar (also known as a right-linear grammar), and how to convert a right-regular rrammar to an NFA. We also defined a regular grammar to be either a right-regular or left-regular grammar. But we have never actually shown that right- and left-regular grammars are equivalent. We will now show how to convert a right-regular grammar to a left-regular grammar.

1. S
2. →
3. aS

1. S
2. →
3. cB

1. B
2. →
3. bB

1. B
2. →
3. b

2. →

F

B

S

a

c

b

b

c

b

F

B

S

a

b

c

b

2. →

2. →

2. →

2. →

2. →

2. →

Saving...
Server Error
Resubmit

35.6.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.