Automata Theory

Unit – 3 [Regular Grammar]

Introduction – 1 [ Part -1]

By Prof. Riju Bhattacharya

Assistant Professor ,
SSIPMT, Raipur
 Agenda
➔ Definition of Regular Grammar

➔ Types of grammar

➔ Finite Automata and Regualr Grammar

2
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Grammar: Definition
 The finite set of rules that used to generate strings called as
Grammar.

OR
 A grammar has 4-tuples G= (V,T,P,S), where

 V is an Variable or Non terminal

 T is a set of terminal symbols
 P set of production
 S start symbol.

3
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Regular Grammar: Definition
 Example

 V={S,A,B,a,b},
 T ={a,b},
 P={S→A, S→B, B→bB, A→aA, A→ε, B→ε},
 S= Start symbol.

4
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Regular Grammar: Example #1
 Let a grammar G={V,T,P,S) where
V = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε,
One derivation from the above CFG is “abaabb” .

5
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Grammar: Tips

 Grammar is generating device.

 Every Grammar has unique start symbol or only one starting

symbol.

 If G is grammar then L(G) is a Language generated by G.

 Every grammar generate only one language but language can

be generated by more than one from the grammar.

 Grammar is not a unique.

6
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Grammar: Tips
 Example: Two grammars G1 & G2 are equal, iff L(G1)=L(G2)

 G1: G2:
S->aA S->BA
A  a
A  b
B  b
S   ab
S   ab
L ( G 1)  { ab } L ( G 2)  { ab }
 L ( G 1)  L ( G 2) but G1  G2
7
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Derivation Tree
 Derivation tree or parse tree is an ordered rooted tree that graphically
represents the process of deriving a string is called as derivation.

 the semantic information of string derived from the CFG.

 If a grammar G has a production α → β, we can say that x α y derives

x β y in G. This derivation is written as −
 xαy⇒Gxβy

8
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Derivations from a Grammar
 Each internal node is labeled with a nonterminal

 If a rule A  A1A2…An occurs in the derivation then A is a parent

node of nodes labeled A1, A2, …, An .

a
S

a S
b
S

9
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Derivation Tree
S A|AB Sample derivations:
A e|a|Ab|AA S  AB  AAB  aAB  aaB  aabB  aabb
B b|bc|Bc|bB S  AB  AbB  Abb  AAbb  Aabb  aabb

• These two derivations use same productions, but in different orders.

• Derivation trees give way to abstract away ordering differences.

S Root label = start node.

A B Each interior label = variable.

A A b B Each parent/child relation = derivation step.

a a b Each leaf label = terminal or e.

All leaf labels together = derived string = yield.

10
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 11
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Leftmost Derivation Tree
• The process of deriving a string by expanding the leftmost non-terminal at each
step is called as leftmost derivation.
• The geometrical representation of leftmost derivation is called as a leftmost derivation tree.

Grammar:
X → X+X | X*X | X | a
Derive a+a*a

The leftmost derivation for the above string

"a+a*a" may be −
X → X+X → a+X → a + X*X → a+a*X → a+a*a

12
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Rightmost Derivation Tree
• The process of deriving a string by expanding the rightmost non-terminal at each
step is called as Rightmost derivation.
• The geometrical representation of rightmost derivation is called as a Rightmost derivation
tree.

Grammar:
X → X+X | X*X | X | a
Derive a+a*a

The rightmost derivation for the above string

"a+a*a" may be −
X → X*X → X*a → X+X*a → X+a*a → a+a*a

13
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 14
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Recursive Grammar
• A grammar is said to be recursive if it contains at least one production that has the
same variable at both its LHS and RHS. OR
• A grammar is said to be recursive if and only if it generates infinite number of
strings.
• A recursive grammar may be either-
1. Left recursive
2. Right recursive

15
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Left Recursive Grammar
• A recursive grammar is said to be left recursive if the leftmost variable of RHS is
same as variable of LHS. OR
• A recursive grammar is said to be left recursive if it has Left Recursion.

Grammar:
S → Sa / b

S → AB
A → Aa / a
B → Bb / b

16
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Right Recursive Grammar
• A recursive grammar is said to be right recursive if the rightmost variable of RHS is
same as variable of LHS. OR
• A recursive grammar is said to be left recursive if it has Right Recursion.

Grammar:
S → aS / b

S → AB
A → aA / a
B → bB / b

17
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Non-Recursive Grammar
• A grammar is said to be non-recursive if it contains no production that has the
same variable at both its LHS and RHS. OR
• A grammar is said to be non-recursive if and only if it generates finite number of
strings.
• Note-
1. A non-recursive grammar has neither left recursion nor right recursion.
Grammar:
S → aA / bB
A→a/b
B→c/d
• The language generated from this grammar is L = { aa , ab , bc , bd }

• Since the grammar generates finite number of strings, therefore it is a non-recursive

grammar.

18
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Recursive Rules:

Rule 1: Rule 2:
A  A | A  A |
A   A  
A  A   A  A   
A    A   2 A  A     2
A     A   3 A  A      3
... ...
 A   *  A  *

19
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Recursive Rules:

Rule 3: Rule 4: Rule 5:

A  A | A  A | e A  aA | bA | e
A   A   *e  A  ( a  b )*
A  A    2  A  *
A  A  3 OR
A  A   4
A  A |e
... A   *e
 A   *  A  *

20
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 find the language generated by the grammar:
• A grammar is a set of production rules which are used to generate strings of a
language.

• Language Generated by a grammar -

• Given a grammar G, its corresponding language L(G) represents the set of all
strings generated from G.

Eg#1 Consider the Grammar:

S → aA / bB Eg#1 Consider the Grammar:
A → b/c L ={ ab, ac, bd}
B→d

21
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
find the language generated by the grammar:

Eg#2 Consider the Grammar:

S → aA / bB L(G):
A → b/c L ={ ab, ac, bd}
B→d

Eg#3 Consider the Grammar:

S → AaB L(G) :
A→a/Ɛ L ={ aab, aac, ab,ac}
B → b/c

22
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
find the language generated by the grammar:

Eg#4 Consider the Grammar:

S → AB / bA L(G):
A → a/b L ={ ac, bc, ba,bb}
B→c

Eg#5 Consider the Grammar:

S → Aa / Bb L(G) :
A → b/c L ={ ba, ca, db, eb}
B → d/e

23
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Find the language generated by the Recursive grammar:

Eg#1 Consider the Grammar: S → a* / b

S → aS / b L(G) ={ an b | n>=0}

Eg#2 Consider the Grammar:

S → AB
S → AB
S → a* b*
A → aA / Ɛ
L(G) ={ am bn | m, n>=0}
B → bB / Ɛ

24
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
find the language generated by the recursive grammar:

Eg#3 Consider the Grammar: S → e , S → ab , S → a2 b2 , S → a3 b3

S → aSb / Ɛ ,…
L(G) ={ an bn | n>=0}

Eg#4 Consider the Grammar: S → ab

S → aA S → abS
A → bS / b S → abS / ab [Ref: Rule 3]
S → (ab)* (ab)
S → (ab)+

L(G) ={ (ab)n | n>=1}

25
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Construct the grammar for the following languages:

Eg#1 Consider the Language: S → aA

L(G) ={ a, ab} A→b/e

S → AB
Eg#2 Consider the Language: A→a
L(G) ={ab, ba} B→b

26
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
Construct the grammar for the following languages:

Eg#3 Consider the Language: S → aX | bX | bX

L(G) ={ aba, bab, bba} X → BA
A→a
A→b

S → aX | XX | bXa
Eg#4 Consider the Language:
X → AB
L(G) ={ aab, abab, baba}
A→a
A→b

27
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar
 Thank You !!

28
Riju Bhattacharya, Dept. of CSE Unit-3-Grammar