1 of 8

Session 1: �Grammar Introduction– Types of Grammar

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 8

Introduction To Grammar�

  • Grammar : It is a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences.
  • Formal Definition of Grammar :
  • Any Grammar can be represented by 4 tuples – <N, T, P, S>
  • N – Finite Non-Empty Set of Non-Terminal Symbols.
  • T – Finite Set of Terminal Symbols.
  • P – Finite Non-Empty Set of Production Rules.
  • S – Start Symbol

Amity School of Engineering & Technology

3 of 8

  • Terminal Symbols – Terminal symbols are those which are the components of the sentences generated using a grammar and are represented using small case letter like a, b, c etc.
  • Non-Terminal Symbols – Non-Terminal Symbols are those symbols which take part in the generation of the sentence but are not the component of the sentence.
  • Production Rules :
  • A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences.
  • It is of the form α-> β where α is a Non-Terminal Symbol which can be replaced by β which is a string of Terminal Symbols or Non-Terminal Symbols.

Amity School of Engineering & Technology

4 of 8

Amity School of Engineering & Technology

5 of 8

Types of Grammer

Amity School of Engineering & Technology

6 of 8

Amity School of Engineering & Technology

7 of 8

Regular Grammer

  • Regular grammar generates regular language. They have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a non-terminal.

​

  • The productions must be in the form:
  • A ⇢ xB
  • A ⇢ x
  • where A, B ∈ Variable(V) and x ∈ T* i.e. string of terminals.

Amity School of Engineering & Technology

8 of 8

Regular Grammer…

  • Types of regular grammar:
  • Left Linear grammar(LLG) and Right linear grammar(RLG)

1. Left linear grammar(LLG):

  • In LLG, the productions are in the form if all the productions are of the form

A ⇢ Bx

A ⇢ x

where A,B ∈ V and x ∈ T*

2. Right linear grammar(RLG):

  • In RLG, the productions are in the form if all the productions are of the form

A ⇢ xB

A ⇢ x

where A,B ∈ V and x ∈ T*

Amity School of Engineering & Technology