S. J. P. N.
TRUST’S
HIRASUGAR INSTITUTE OF TECHNOLOGY, NIDASOSHI
Accredited at 'A+' Grade by NAAC
Programmes Accredited by NBA: CSE, ECE
Department of Computer Science & Engineering
.IN
Course: Theory of Computation(BCS503)
C
Module 3: Context Free Grammar &
N
SY
Pushdown Automata
U
VT
Prof. A. A. Daptardar
Asst. Prof. , Dept. of Computer Science &
Engg.,
1
Hirasugar Institute of Technology, Nidasoshi
Module-3
Content to be covered:
.IN
• Context-Free Grammars, Parse Trees,
C
Ambiguity in Grammars and Languages,
N
Ambiguity in Grammars and Languages,
SY
Definition of the Pushdown Automaton,
U
The Languages of a PDA, Equivalence of
VT
PDA's and CFG's, Deterministic
Pushdown Automata.
• TEXT BOOK: Sections 5.1, 5.2, 5.4,
6.1,6.2,6.3.1,6.4 2
.IN
CONTEXT FREE GRAMMARS
C
N
AND LANGUAGES
SY
U
Context free grammars
VT
Parse Trees
Ambiguity in Grammars and Languages
3
VT
U
SY
N
C
Grammar
.IN
4
What is Grammar?
.IN
C
N
SY
U
VT
5
Components of Grammar
.IN
C
N
SY
U
VT
6
Notations used while
constructing the Grammar
.IN
C
N
SY
U
VT
7
Chomsky Hierarchy of Languages
.IN
Languages from “simplest” to “complex”
Each is a subset of the ones below
C
N
• Regular
• Context Free SY
U
• Context Sensitive
VT
• Recursively Enumerable
Can be defined by the type of
Machine that will recognize it. Noam Chomsky 8
Obtaining Grammar from FA
.IN
C
N
SY
U
VT
9
VT
U
SY
N
C
.IN
10
VT
U
SY
N
C
.IN
11
Another method
.IN
C
N
SY
U
VT
12
VT
U
SY
N
C
.IN
13
VT
U
SY
N
C
.IN
14
VT
U
SY
N
C
.IN
15
VT
U
SY
N
C
.IN
16
VT
U
SY
N
C
.IN
17
VT
U
SY
N
C
.IN
18
VT
U
SY
N
C
.IN
19
VT
U
SY
N
C
.IN
20
VT
U
SY
N
C
.IN
21
Alternate Method
.IN
C
N
SY
U
VT
22
.IN
OBTAINING GRAMMAR FROM
C
N
RE
SY
U
VT
23
VT
U
SY
N
C
.IN
24
VT
U
SY
N
C
.IN
25
VT
U
SY
N
C
.IN
26
.IN
C
LANGUAGE
N
SY
U
What is the Language Generated by Grammar?
VT
27
VT
U
SY
N
C
.IN
28
VT
U
SY
N
C
.IN
29
VT
U
SY
N
C
.IN
30
VT
U
SY
N
C
.IN
31
VT
U
SY
N
C
.IN
32
VT
U
SY
N
C
.IN
33
VT
U
SY
v
N
C
.IN
34
VT
U
SY
N
C
.IN
35
VT
U
SY
N
C
.IN
36
VT
U
SY
N
C
.IN
37
VT
U
SY
N
C
.IN
38
VT
U
SY
N
C
.IN
39
VT
U
SY
N
C
.IN
40
VT
U
SY
N
C
.IN
41
VT
U
SY
N
C
.IN
42
VT
U
SY
N
C
.IN
43
VT
U
SY
N
C
.IN
44
VT
U
SY
N
C
.IN
45
.IN
C
DERIVATION
N
SY
U
VT
46
VT
U
SY
N
C
.IN
47
VT
U
SY
N
C
.IN
48
.IN
C
LEFTMOST DERIVATION
N
SY
U
VT
49
Definition
• If a word w is generated by z CFG by a
.IN
certain derivation, and at each step in the
C
derivation a rule of production is applied to
N
the leftmost nonterminal in the working
SY
string, then this derivation is called a
U
leftmost derivation.
VT
50
VT
U
SY
N
C
.IN
51
VT
U
SY
N
C
.IN
52
.IN
C
RIGHTMOST DERIVATION
N
SY
U
VT
53
Definition
• If a word w is generated by z CFG by a
.IN
certain derivation, and at each step in the
C
derivation a rule of production is applied to
N
the rightmost nonterminal in the working
SY
string, then this derivation is called a
U
leftmost derivation.
VT
54
VT
U
SY
N
C
.IN
55
VT
U
SY
N
C
.IN
56
.IN
DERIVATION TREE /
C
N
PARSE TREE
SY
U
VT
57
VT
U
SY
v
N
C
.IN
58
.IN
C
AMBIGUOUS GRAMMAR
N
SY
U
VT
59
Definition
• A CFG is called ambiguous of for atleast
.IN
one word in the language that it generates
C
two or more possible derivations of the
N
word that corresponds to different
SY
derivation trees.
U
• OR
VT
• If a grammar G generates two different
derivation trees for the same string is
called ambiguous grammar.
60
VT
U
SY
v
N
C
.IN
61
VT
U
SY
N
C
.IN
62
VT
U
SY
N
C
.IN
63
VT
U
SY
N
C
.IN
64
VT
U
SY
N
C
.IN
65
VT
U
SY
N
C
.IN
66
VT
U
SY
N
C
.IN
67
VT
U
SY
N
C
.IN
68
VT
U
SY
N
C
.IN
69
.IN
C
PUSH DOWN AUTOMATA
N
SY
U
VT
PDA
70
Is there any need of Push Down Automata
when FINITE AUTOMATA is there?
.IN
C
N
SY
U
VT
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
NOTE
.IN
PDA definition:
.IN
C
N
SY
U
VT
Transition function:
.IN
C
N
SY
U
VT
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
INSTANTANEOUS
C
N
DESCRIPTION
SY
U
VT
80
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
Acceptance of a language by
PDA
• There are two cases wherein a string w is
.IN
accepted by a PDA.
C
– Get the final state from the start state.
N
SY
– Get an empty stack from the start state
• In the first case, we say that the language
U
is accepted by a final state and in the
VT
second case we say that the language is
accepted by an empty stack or null stack.
83
• The formal definitions to accept the string
by a final state and by an empty stack are
defined as follows.
.IN
C
N
SY
U
VT
84
• For w ϵ Ʃ*, q0,p ϵ Q . It means that when
.IN
the string w is accepted by an empty
C
stack, the final state is irrelevant, the input
N
should be completely read and the stack
SY
should be empty. Here the state p is not
U
the final state, only thing is that the string
VT
w should be completely read and stack
should be empty.
85
.IN
C
CONSTRUCTION OF PDA
N
SY
U
VT
86
VT
U
SY
N
C
.IN
• General Procedure: To check for the palindrome, let us push
all scanned symbols onto the stack till we encounter the letter C.
Once we pass the middle string, if the string is a palindrome, for
each scanned input symbol, there should be a corresponding
symbol (same as input symbol) on the stack. Finally, if there is no
.IN
input and stack is empty, we say that the given string is a
palindrome.
C
• Step 1: Input symbols can be a or b.
N
Let q0 be the initial state and Z0 be the initial symbol on
SY
the stack. In state q0 and when top of the stack is Z0
whether the input symbol is a or b push it on to the stack
U
and remain in q0. The transitions defined for this can be
VT
of the form
88
• Once the first scanned input symbol is pushed on the
stack, the stack may contain either a or b. Now, in state
q0, the input symbol can be either a or b. Note that
irrespective of what is the input or what is there on the
.IN
stack, we have to keep pushing all the symbols on to the
stack, till we encounter C. So, the transitions defined for
C
this can be of the form
N
SY
U
VT
• Step 2: Input symbol is C.
Now, if the next input symbol is C, the top of the stack
may be a or b. Another possibility is that, in state q0, the
.IN
first symbol itself can be C. In this case w is null string
and Z0 will be on the stack. In all these cases, the input
C
symbol is C i.e. the symbol which is present in the
N
middle of the string. So, change the state to q1 and don
SY
not alter the contents of the stack, The transitions for this
can be of the form
U
VT
Now we have passed the middle of the string
90
• Step 3: Input symbols can be either a or b.
To be a palindrome, for each input symbol there should
be a corresponding symbol(same as input symbol) on the
.IN
stack. So, whenever the input symbol is same as symbol
on the stack, remain in state q1 and delete that symbol
C
from the stack and repeat the process. The transitions
N
defined for this can be of the form
SY
U
VT
• Step 4 : Finally, in state q1, if the string is a palindrome,
there is no input symbol to be scanned and the stack
should be empty i.e. the stack should contain Z0. Now,
change the state to q2 and do not alter the contents of the
stack. The transition for this can be of the form
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
v
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
C
Deterministic PDA
N
SY
U
VT
107
Deterministic PDA
.IN
C
N
SY
U
VT
108
• Example: Is the PDA to accept the language
L(M) = {wCwR | w ϵ (a+b)* } is deterministic?
• Solution: The transitions defined for this machine
are obtained as follows:
.IN
C
N
SY
U
VT
109
VT
U
SY
N
C
.IN
110
VT
U
SY
N
C
.IN
111
VT
U
SY
N
C
.IN
112
VT
U
SY
N
C
.IN
113
VT
U
SY
N
C
.IN
114
.IN
C
CFG TO PDA
N
SY
U
VT
115
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
C
APPLICATIONS OF GNF
N
SY
U
VT
Obtain CFG,
Convert it into GNF,
Then Obtain the PDA 126
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
.IN
C
PDA TO CFG
N
SY
U
VT
132
Procedure to convert pda to
cfg:
.IN
C
N
SY
U
VT
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
VT
U
SY
N
C
.IN
