Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Regular Grammar
2.1.
Types of Regular Grammar
3.
Conversion of Finite Automata To Regular Grammar
4.
Frequently Asked Questions
4.1.
Regular Grammar belongs to which type in Chomsky Hierarchy?
4.2.
What are the different types of Regular Grammar?
4.3.
What does Φ signify in a regular expression?
5.
Conclusion
Last Updated: Mar 27, 2024

Regular Grammar

Author Rajat Agrawal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
TOC

Introduction

A Grammar ‘G’ can be formally described using four tuples as G = (V, T, S, P) where,

V = Set of Variables or Non-Terminal Symbols

T = Set of Terminal Symbols

S = Start Symbol

P = Production Rules for Terminals and Non-Terminals

A production rule has the form 𝛂→𝛃 where 𝛂 and 𝛃 are strings on V ⋃ T, and at least one symbol of  𝛂 belongs to V.

Example: G = ({S, A, B}, {a, b}, S, {S→AB, A→a, B→b})

Noam Chomsky gave a Mathematical model of Grammar, which is effective for computer Languages.

According to Chomsky, four types of Grammar exist(see Chomsky Hierarchy), and Type-3 grammar is the Regular Grammar that accepts Regular Languages.

Let’s understand the concepts of Regular Grammar in-depth.

Also See, Moore Machine

Regular Grammar

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

They have a single non-terminal symbol on the left-hand side, a single terminal on the right-hand side, or a single terminal followed by a non-terminal.

Regular Grammar accepts and generates regular languages.

All the productions should be in the form of:

A –> xB
A –> x
A –> Bx


where A, B ∈ V (Set of Variables), and x ∈ T*, i.e., the string of terminals.

Read About - Simplification of CFG

Types of Regular Grammar

Regular Grammar can be divided into two types:-

1.) Left Linear Grammar (LLG)

2.) Right Linear Grammar (RLG)

1.) Left Linear Grammar(LLG): A grammar is said to be Left Linear if all productions are of the form:

A –> Bx
A –> x


where A, B ∈ V (Non-Terminal Symbols), and x ∈ T*, i.e., the string of terminals.

In LLG, the non-terminal symbol lies on the Left of the terminal symbol.

2.) Right Linear Grammar(RLG): A grammar is said to be Right Linear if all productions are of the form:

A –> xB
A –> x


where A, B ∈ V (Non-Terminal Symbols), and x ∈ T*, i.e., the string of terminals.

In RLG, the non-terminal symbol lies on the Right of the terminal symbol.

The Regular Grammar generates regular language, for which we can design FA, and FA can also be converted into Regular Grammar.

In the next section, we will see how to convert an FA into Regular Grammar.

Also see, Turing Machine in TOC.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Conversion of Finite Automata To Regular Grammar

Example:  FA for accepting strings that start with 1.

Example Automaa
∑  = {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.

RLG

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 1

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:


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!!

Next article
Context-Free Grammar and Language
Live masterclass