## 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____.__