Regular Grammar

Conversion of Finite Automata To Regular Grammar

Example:  FA for accepting strings that start with 1.

∑  = {0,1}
Initial state(q0) = A
Final state(F)  = B

The RLG corresponding to FA is:

A –> 1B   
B –>  ∈/0B/1B 

The above grammar is RLG, which can be written directly through FA.

The above RLG can derive strings that start with 1 and after that any input symbol (i.e. ∑ = {0, 1} can be accepted).

The regular language corresponding to RLG is

L= {1, 10, 11, 100, 101, 110, 111 ..... }

If we reverse the production of the above RLG, then we get:

A –> B1   
B –>  ∈/B0/B1 

It derives the language containing all the strings, ending with 1.

i.e. L' = {1, 11, 01, 001, 101, 011, 111 .....}

Conclusion: If we have Finite Automata that represents language L and converts it into RLG, that again represents the same language L, but after reversing RLG, we get LLG that represents language L'(i.e., reverse of L).

To convert the RLG into LLG for language L, the following steps needs to be followed:-

Step 1: Reverse the given FA for language L.

Step 2: Convert FA to RLG.

Step 3: Reverse the RLG.

After following these three steps, we will get the grammar that generates the language representing the LLG for the same language, L.

Let’s apply these steps to the example we have taken above, i.e., set all strings over input symbols 0 and 1, starting with 1. We are converting it into LLG.

Step 1: The reversal of FA is

Step 2: The corresponding RLG for this reversed FA is

B –> 0B/1B/1A
A –> ∈

Step 3: The reversing the above RLG, we get

B –> B0/B1/A1
A –> ∈

So this is the LLG for language L( which represents all strings that start with 1).

L= {1, 10, 11, 100, 101, 110, 111 ….. }

Also read, Arden's theorem

Frequently Asked Questions

Regular Grammar belongs to which type in Chomsky Hierarchy?

Regular Grammar is the Type-3 grammar according to Chomsky Hierarchy. 

What are the different types of Regular Grammar?

There are two types of Regular Grammar: 1. Left Linear Grammar (LLG); 2.Right Linear Grammar (RLG)

What does Φ signify in a regular expression?

Φ is a regular expression that denotes the empty set.

Conclusion

In this blog, we have learned about Regular Grammar, the type of RG, and conversion from FA to Regular Grammar.

Recommended Readings:

• Basics of TOC
• Finite State Machine
• Automata Theory
• Regular Grammar
• Symbol Table Operations
• Regular Expression
• Regular Expression And Finite Automata 
• Context-Free Grammar and Language.
• DFA minimization

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. 

Happy Learning!!