Grammar in Automata

Grammar in automata theory is a standard way of representing the language. The grammar contains a set of production rules that make up the language strings. The set of all possible strings that can be derived from grammar is known as the language of that grammar. The symbol “G” mostly denotes a grammar.

Real-Life Example of Grammar in Automata

Grammar is just the same as English Grammar. If the sentence is grammatically correct, it will be part of grammar; otherwise, it will not. The following is a real-life example of grammar in automata 

  • “I am going to school”. It is a valid example of grammar.
  • I going am to school. It is not a valid example of grammar.

Elements of Grammar in Automata

To get a better understanding of grammar, we first understand its elements. Elements of Grammar depend on the types of grammar. The essential elements of grammar are given below.

G = (V, T, P, S) Where V, T, P, S are the elements of Grammar (G).

1. V  (Variables also called Non-Terminal)

  • Capital symbols represent a finite number of non-empty sets, i.e., A, B, C.
  • It’s not a part of the string, which makes after-production rules.

2. T (Terminal)

  • A finite set of Alphabets (Σ), Represented by small letters, i.e., a,b,c.
  • All variables are replaced with non-terminals through production rules.
  • Terminals are part of the string, which makes a production rule.

3. P (Production Rules)

  • The finite set of non-empty rules to make a string of language
  • i.e. P = { S → aSb , S → bSa , S → ∈ }   

4. S (Start symbol)

The start symbol is used to start the production rule represented by S.

Note: Above grammar generates the strings through production rules having equal number of a’s and b’s. As given Below

L = {ab, aabb, aaabbb, …….}

Example of Grammar in Automata

Consider a grammar G = (V, T, P, S) where

  • V = { S }                                                  // Set of Non-Terminal symbols
  • T = { 0 , 1 }                                              // Set of Terminal symbols
  • P = { S → 0S1S , S → 1S0S , S → ∈ }   // Set of production rules
  • S = { S }                                                   // Start symbol

This grammar generates the strings having an equal number of 0’s and 1’s.

Equivalent Grammars in Automata

Two grammars will be equivalent if and only if they both generate the same languages.

Grammar G1: Consider Grammar 1 (G1) with the following production Rules.

  • S → aSb
  • S → ∈

Grammar G2: Consider Grammar 2 (G2) with the following production Rules.

  • S → aAb / ∈
  • A → aAb / ∈

Result: The above Grammar (G1 and G2) will generate the same language.

L = { anbn , n>=0 }

So, L(G1) = L(G2). 

It can be represented as

∴ G1 ≡ G2

Types of Grammars in Automata

There are three significant categories of grammar, as explained in the following diagram

Types of Grammar - Theory Of Automata