Theory of Automata

1
Lecture 10
Amna Iftikhar

Amna Iftikhar Spring 23

Week 3

CFGs
 3

Context-free grammars (CFGs)
 Context-free grammars (CFGs) are used to describe context-free
languages.

 A context-free grammar is a set of recursive rules used to generate

patterns of strings.

 A context-free grammar can describe all regular languages and

more, but they cannot describe all possible languages.
 4
 One can provide a formal definition of a context free grammar.

 It is a 4-tuple (V, Σ, S, P) where:

 V is a finite set of variables (In Upper case);

Σ is a finite alphabet of terminals (In lower case);

S is the start variable; and

 P is the finite set of productions.

 5
Context Free Grammar
 'Context' in case of a grammar refers to the position or setting in which a
symbol appears in a string.
 More precisely the symbols that precede or succeed a particular
symbol(terminal or non-terminal), determine its context.

 A formal grammar is considered "context free" when

 its production rules can be applied regardless of the context of a
nonterminal.

 No matter which symbols surround it,

 the single nonterminal on the left hand side can always be replaced by
the right hand side.
 6
Context Free Grammar
 A grammar consists of:
 a set of variables one of which is designated the start variable; It
is customary to use upper-case letters for variables;

a set of terminals (from the alphabet); and

a list of productions (also called rules).

 7

 S as a start variable:

S V | VV | t | V t | t V

 V is any Non-terminal Variable

 A A | AB | a | Aa | b B | ᵋ
 8
Symbols used in CFG

Symbol in Example Symbol in Example

RE CFG
+ a+b | a|b
* ,+ a Recursive
definition
Aa

*
 9

Some rules for using Production.

 Left Side of Every Production contains only One Variable

 On right side of any production it may be only V or only t or any

combination of V and t

 A A | AB | a | Aa | b B | ᵋ
 10
Examples:
 CFG for the language that contain words of one length
character

 RE = a + b
 CFG : S→A
S →a | b A→ a | b

 CFG for the language that contain words of two length

character.

 RE = (a + b)(a + b)
 CFG : S →AA
S → aa | ab | ba | bb A→a |b
 11
Examples:
 CFG for the language that contain at most 3 character words
 RE
ᵋ ᵋ
= (a + b + ) (a + b + ) (a + b + )ᵋ
 CFG :
S →A AA
A → a|b|
ᵋ
 CFG for the language that contain at most 3 character words, but start with
a.
 RE
ᵋ ᵋ
= a(a + b + ) (a + b + )
 CFG : AA

ᵋ
S →a
A → a|b|
 12
Examples:

 CFG for the language that contain only single a. Σ = {a}

 RE = a
 CFG :
S →a
S S

 CFG for the language that contain at least one a. Σ = {a} A A

 RE = a+ {a,aa,aaa,aaaa,…………..}
 CFG : a A a

S →A
a
 A → Aa |a
aa
 13
Examples:
 CFG for the language that contain at least one a. Σ = {a}
 RE = a+ {a,aa,aaa,aaaa,…………..}
 CFG :
S →A S→A
 A → Aa |a A → aA
A→ a
 CFG for the language that contains words of any length. Σ = {a,b} S → AB
S→A A → aA
 RE = (a+b)* S →A A → aA A→ a
 CFG : A → aA A→a A→ ᵋ
S →A A→a
A → bA
A→
A→B
ᵋ A→ B
B → bB
A → aA | a | b | bA |
ᵋ A→b B → bB B→b
A→ ᵋ B→b
B→ ᵋ
B→
B→A
ᵋ B→A
 14
Examples:
 CFG for the language that contain at least one a. Σ = {a}
 RE = a+ {a,aa,aaa,aaaa,…………..}
 CFG :
S →A S→A
 A → Aa |a A → aA
A→ a
 CFG for the language that contains words of any length. Σ = {a,b}
 RE = (a+b)* S →A
 CFG : A → aA
S →A A→a
A → bA
A → aA | a | b | bA |
ᵋ A→b
A→ ᵋ
 15
CFG Continues…..
 CFG for a language that contains at least two characters
with start and end with same symbol
S
 CFG:
 S → aAa P-1
a a S → aAa | bAb
A
 S → bAb P-2 A→ aA | bA | a | b
 A → aA P-3
b A
 A → bA P-4
 A→a P-5 a A
 A→b P-6
 A→
ᵋ P-7 b A

 Word to generate: ababbaa

b A
 Sequence of Production to use
P1 ═>P4 ═>P3 ═>P4 ═>P4 ═>P5 a
 16
 Language that contains b as a third last character
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB
A → aA | bA | a | b |
B→ a | b
ᵋ
 S → AbBB P-1
 A → aA P-2
 A → bA P-3
 A→ a P-4
 A→ b P-5
 A→
ᵋ P-6
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 17
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
 S → AbBB P-1
 A → aA P-2
 A → bA P-3
 A→a P-4
A→b P-5
ᵋ P-6

A→
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 18
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A
 S → AbBB P-1
 A → aA P-2
 A → bA P-3
 A→a P-4
 A→b P-5 A→
ᵋ P-6
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 19
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
 A→a P-4
A→b P-5
ᵋ P-6

A→
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 20
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
a A
 A→a P-4
 A→b P-5 A→
ᵋ P-6
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 21
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b|
B→ a | b
ᵋ
b A
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
a A
 A→a P-4
A→b P-5
ᵋ P-6

A→
 B→ a P-7 a
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 22
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A a
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
a A
 A→a P-4
A→b P-5
ᵋ P-6

A→
 B→ a P-7 a
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 23
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A a b
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
a A
 A→a P-4
A→b P-5
ᵋ P-6

A→
 B→ a P-7 a
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 24
 Language that contains b as a third last character S
 RE: (a+b)*b(a+b)(a+b)
 CFG: S →AbBB A b B B
A → aA | bA | a | b |
B→ a | b
ᵋ
b A a b
 S → AbBB P-1
 A → aA P-2 a A
 A → bA P-3
a A
 A→a P-4
 A→b P-5 A→
ᵋ P-6 a
 B→ a P-7
 B→ b P-8
 Word :- baaabab
 Sequence of Productions:-
 P1→P3→P2 →P2 →P4 →P7 →P8
 25
 CFG for a programming variable.
 CFG;
 S →MO
 M → a | b |c…….|z
 O → M | OM | 1O |2O |….|9O |_O |
ᵋ

 X
 Xy
 X123
 Number_1
 26
CFG for Arithmetic Expression S
 AE = a+(b*c)
E
 CFG:
 S→E P-1
E + E
 E → (E) P-2
 E→E+E P-3 a ( E )
 E→E*E P-4
 E→a P-5
E * E
 E→b P-6
 E→ c P-7 b c

 Production Sequence:
 P1 → P3 → P5(L) → P2(R) →P4(C) →P6(L) →P7(R)
27