Theory of
Computer
Science
N
O
UNIVERSITY OF MUMBAI
TE
Computer Engineering/SEM V
S
B
Revised syllabus (Rev- 2016)
Y
A
K
,Contents
FSM page1
Ends With
100 page2
Bba page4
Abb, 1011, 101 or 110 page5
011 page7
Second last symbol is “a” page6
Contains
Aba, 110 page6
Does not contain 010 page7
N
Does not contain 3 consecutive a’s, contains atleast 2 a’s page8
O
contains atleast 3 a’s page9
3 a’s page9
TE
Contains atmost 3 a’s, odd no of a’s page10
Even no of a’s, even a’s and odd b’s, odd a’s and even b’s page11
S
Divisibility
Binary no divisible by 3, by 4 page12
B
Ternary no by 5 page13
Regular Expression page14
Y
RE to NFA page17
a(a+b)*b page19
A
(ab + ba)* page20
K
Strings ending in “aa” page20
(0+1)*(10)*(0+1) page21
(0+E) (10)*(1+E) page21
Strings that end either in 01 or 101 page22
DFA page22
Strings ending in “aa” page24
R = (11 + 10)* page25
R = 0*1*2* page26
R = (10 + 01)* page27
Convert NFA with epsilon to DFA page28
NFA with epsilon to without page30
NFA without epsilon to DFA page31
Finite Automata to RE page33
,Direct DFA construction
Strings ending in 100 page38
Strings ending in 1011, contains 110 page39
Does not contain 010, contains atleast 2a’s page40
Atmost 3a’s page41
Binary no divisible by 3, by 5 page42
Beginning with 1 and decimal value multiple of 5 page43
Language containing all strings over {a,b,c} that starts and
page43
ends with different symbols
Differentiate DFA and NFA page44
Moore and Mealy page44
Moore Machine
Output ‘A’ if input ending in 101, ‘B’ if 110 and ‘C’ otherwise page45
N
Output the remainder when binary no is divided by 3 page47
O
Output the remainder when ternary no is divided by 5
Change each occurrence of 110 to 111 page48
TE
Change each occurrence of abb to aba
Mealy Machine
S
Output ‘A’ if ending in bba and ‘R’ otherwise page49
Output even/odd no of a’s
B
Output the remainder when binary no is divided by 3 page50
Change each occurrence of 110 to 111
Y
Change each occurrence of abb to aba
page51
Binary adder
A
Differentiate Moore and Mealy page52
K
Moore to mealy and vice-versa page53
Design Moore and Mealy machine to find 1’s complement of
binary number page55
2’s complement
Mealy/Moore machine for r = (0+1)*(00+11)
page56
(ab aur 10 ka dhyaan rakhna)
Grammars
Chomsky’s Hierarchy page57
CFG (derivation) page58
S -> aAS | a
A -> SbA | SS | ba
page59
Derive “aabbaa” using LMD & RMD. Draw parse tree.
,S -> aB | bA
A –> a | aS | bAA
B -> b | bS | aBB
Derive aabb, baab, aab
S -> SAS | b
A -> ba | b page60
String “bbabbbbab”
Ambiguous grammar page62
S -> iCtS | iCtSeS | a
C -> b page62
String “ibtibtaea”
Writing Grammar/CFG/CFL
Start with a over {a,b}
N
End in 10 page64
O
End either in 00 or 11
Start with a and end with b
TE
Contain aa page65
Contain atleast/exactly/atmost 2 a’s
L = {an bn | n >= 1}
S
L = {an b2n | n >= 1}
page66
B
L = {a2n bn | n >= 0}
L = {am bm-3 | m >= 3}
Y
Simplification of CFG page67
S –> aS | B
A
page69
B -> b | c
K
S -> aSb | A
page70
A -> c | epsilon
Chmosky normal form (CNF)
S -> aA | a page71
A -> aSa | b
S -> XYX
X -> aX | a
Y -> bY | b
page72
S -> ASA | a
A -> bA | c | b
S -> aB | bA
A -> a | aS | bAA page73
B -> b | bS | aBB
,S -> Sa | A
page74
A -> a | b
S -> aSb | bSa | epsilon page75
S -> ABA
A -> aA | bA | epsilon page76
B -> bB | aA | epsilon
Greibach Normal Form (GNF)
page77
S -> ASA | AA
A -> bA | c | b
S -> AB | BA | ABA
A -> aA | b
B -> bB | a
N
page78
O
S -> AB
A -> BSB | BB | b
TE
B -> a
S -> ad | aA
A -> aSa | b
S
page79
B
S -> ASB | a | bb
A -> aSA | a
Y
B -> SbS | bb
S -> AS | a
A
A -> SA | b
K
page80
X -> YY | a
Y -> XX | b
S -> SS | aSb | ab page81
S -> XA | BB
B -> b | SB
X -> b
A -> a page82
S -> aSb | aX
X -> Xa | Sa | a
Push Down Automata (PDA)
page83
Model
Design PDA to recognize L = {an bn | n >= 1} page84
,L = {0n 1n | n >= 1} page86
L = {an b2n | n >= 1} page87
L = {cn d3n | n >= 1} page88
L = {an bm cm dn| n >= 1}
L = {an bm an | m, n >= 1}
page89
L = { WCWr | w – any combination of a’s and b’s
wr is reverse of w}
Language containing equal number of a’s and b’s page90
Language containing num of a’s are greater than num of b’s page91
Check well formedness of parentheses page92
CFG to PDA
N
page93
O
S -> aSb | bb
PDA to accept the language L = {a2n bn | n > 0} page94
TE
L = {an+1 b2n+1 | n >= 1} page95
Turing Machine
page96
S
Model
L = {an bn | n >= 1} page97
B
L = {an bn cn| n >= 1} page98
L = {an b2n | n >= 1} page99
Y
L = {a2n bn | n >= 1} page100
Equal no of a’s and b’s
A
page101
No of a’s greater than no of b’s
K
Check for palindrome page102
Perform m monus n page103
Perform m+n page104
Check well formedness of parentheses
page105
Types of TM
Perform m*n
i/p: B0m | 0n B
page106
o/p: B0pB
p = m*n
Applications of TCS page107
Pumping Lemma by proof of Contradiction
page109
L = { aibi | i >= 1}
L = { aib2i | i > 0} page110
,L = { 0i^2 | I >= 1} page111
PDA for L = { aibi ci| i >= 1} page112
L = { ai| I is prime} is not CFL page113
N
O
TE
S
B
Y
A
K
, K
A
Y
B
S
TE
O
N
, N
O
TE
S
B
Y
A
K
Computer
Science
N
O
UNIVERSITY OF MUMBAI
TE
Computer Engineering/SEM V
S
B
Revised syllabus (Rev- 2016)
Y
A
K
,Contents
FSM page1
Ends With
100 page2
Bba page4
Abb, 1011, 101 or 110 page5
011 page7
Second last symbol is “a” page6
Contains
Aba, 110 page6
Does not contain 010 page7
N
Does not contain 3 consecutive a’s, contains atleast 2 a’s page8
O
contains atleast 3 a’s page9
3 a’s page9
TE
Contains atmost 3 a’s, odd no of a’s page10
Even no of a’s, even a’s and odd b’s, odd a’s and even b’s page11
S
Divisibility
Binary no divisible by 3, by 4 page12
B
Ternary no by 5 page13
Regular Expression page14
Y
RE to NFA page17
a(a+b)*b page19
A
(ab + ba)* page20
K
Strings ending in “aa” page20
(0+1)*(10)*(0+1) page21
(0+E) (10)*(1+E) page21
Strings that end either in 01 or 101 page22
DFA page22
Strings ending in “aa” page24
R = (11 + 10)* page25
R = 0*1*2* page26
R = (10 + 01)* page27
Convert NFA with epsilon to DFA page28
NFA with epsilon to without page30
NFA without epsilon to DFA page31
Finite Automata to RE page33
,Direct DFA construction
Strings ending in 100 page38
Strings ending in 1011, contains 110 page39
Does not contain 010, contains atleast 2a’s page40
Atmost 3a’s page41
Binary no divisible by 3, by 5 page42
Beginning with 1 and decimal value multiple of 5 page43
Language containing all strings over {a,b,c} that starts and
page43
ends with different symbols
Differentiate DFA and NFA page44
Moore and Mealy page44
Moore Machine
Output ‘A’ if input ending in 101, ‘B’ if 110 and ‘C’ otherwise page45
N
Output the remainder when binary no is divided by 3 page47
O
Output the remainder when ternary no is divided by 5
Change each occurrence of 110 to 111 page48
TE
Change each occurrence of abb to aba
Mealy Machine
S
Output ‘A’ if ending in bba and ‘R’ otherwise page49
Output even/odd no of a’s
B
Output the remainder when binary no is divided by 3 page50
Change each occurrence of 110 to 111
Y
Change each occurrence of abb to aba
page51
Binary adder
A
Differentiate Moore and Mealy page52
K
Moore to mealy and vice-versa page53
Design Moore and Mealy machine to find 1’s complement of
binary number page55
2’s complement
Mealy/Moore machine for r = (0+1)*(00+11)
page56
(ab aur 10 ka dhyaan rakhna)
Grammars
Chomsky’s Hierarchy page57
CFG (derivation) page58
S -> aAS | a
A -> SbA | SS | ba
page59
Derive “aabbaa” using LMD & RMD. Draw parse tree.
,S -> aB | bA
A –> a | aS | bAA
B -> b | bS | aBB
Derive aabb, baab, aab
S -> SAS | b
A -> ba | b page60
String “bbabbbbab”
Ambiguous grammar page62
S -> iCtS | iCtSeS | a
C -> b page62
String “ibtibtaea”
Writing Grammar/CFG/CFL
Start with a over {a,b}
N
End in 10 page64
O
End either in 00 or 11
Start with a and end with b
TE
Contain aa page65
Contain atleast/exactly/atmost 2 a’s
L = {an bn | n >= 1}
S
L = {an b2n | n >= 1}
page66
B
L = {a2n bn | n >= 0}
L = {am bm-3 | m >= 3}
Y
Simplification of CFG page67
S –> aS | B
A
page69
B -> b | c
K
S -> aSb | A
page70
A -> c | epsilon
Chmosky normal form (CNF)
S -> aA | a page71
A -> aSa | b
S -> XYX
X -> aX | a
Y -> bY | b
page72
S -> ASA | a
A -> bA | c | b
S -> aB | bA
A -> a | aS | bAA page73
B -> b | bS | aBB
,S -> Sa | A
page74
A -> a | b
S -> aSb | bSa | epsilon page75
S -> ABA
A -> aA | bA | epsilon page76
B -> bB | aA | epsilon
Greibach Normal Form (GNF)
page77
S -> ASA | AA
A -> bA | c | b
S -> AB | BA | ABA
A -> aA | b
B -> bB | a
N
page78
O
S -> AB
A -> BSB | BB | b
TE
B -> a
S -> ad | aA
A -> aSa | b
S
page79
B
S -> ASB | a | bb
A -> aSA | a
Y
B -> SbS | bb
S -> AS | a
A
A -> SA | b
K
page80
X -> YY | a
Y -> XX | b
S -> SS | aSb | ab page81
S -> XA | BB
B -> b | SB
X -> b
A -> a page82
S -> aSb | aX
X -> Xa | Sa | a
Push Down Automata (PDA)
page83
Model
Design PDA to recognize L = {an bn | n >= 1} page84
,L = {0n 1n | n >= 1} page86
L = {an b2n | n >= 1} page87
L = {cn d3n | n >= 1} page88
L = {an bm cm dn| n >= 1}
L = {an bm an | m, n >= 1}
page89
L = { WCWr | w – any combination of a’s and b’s
wr is reverse of w}
Language containing equal number of a’s and b’s page90
Language containing num of a’s are greater than num of b’s page91
Check well formedness of parentheses page92
CFG to PDA
N
page93
O
S -> aSb | bb
PDA to accept the language L = {a2n bn | n > 0} page94
TE
L = {an+1 b2n+1 | n >= 1} page95
Turing Machine
page96
S
Model
L = {an bn | n >= 1} page97
B
L = {an bn cn| n >= 1} page98
L = {an b2n | n >= 1} page99
Y
L = {a2n bn | n >= 1} page100
Equal no of a’s and b’s
A
page101
No of a’s greater than no of b’s
K
Check for palindrome page102
Perform m monus n page103
Perform m+n page104
Check well formedness of parentheses
page105
Types of TM
Perform m*n
i/p: B0m | 0n B
page106
o/p: B0pB
p = m*n
Applications of TCS page107
Pumping Lemma by proof of Contradiction
page109
L = { aibi | i >= 1}
L = { aib2i | i > 0} page110
,L = { 0i^2 | I >= 1} page111
PDA for L = { aibi ci| i >= 1} page112
L = { ai| I is prime} is not CFL page113
N
O
TE
S
B
Y
A
K
, K
A
Y
B
S
TE
O
N
, N
O
TE
S
B
Y
A
K
