Exam Details
| Subject | theory of computer science (paper – iv) | |
| Paper | ||
| Exam / Course | b.sc. – i (ecs) | |
| Department | ||
| Organization | solapur university | |
| Position | ||
| Exam Date | November, 2018 | |
| City, State | maharashtra, solapur |
Question Paper
B.Sc. III (Semester (Old CGPA) Examination, 2018
theory of computer science (Paper IV)
Day and Date Thursday, 22-11-2018 Total Marks 70
Time 2.30 p.m. to 5.00 p.m.
Instructions All questions are compulsory.
Figures to the right indicate full marks.
1. Choose correct alternatives. 14
All possible subset of set is known as
sub set power set
super set None of these
Proper prefix of the string abc
The empty string is denoted by
ε
Both a and b None of these
Function which mapping one to one from input to output such function is
known as function.
Machine State
Both a and b None of these
Push Down Automata has tuples.
4 5 6 7
Number of states requires accepting string ends with 10.
3 2
1 can't be represented
Set P
NFA is more powerful than DFA.
True False
A finite automata with output has final states.
True False
Regular expression denotes the set
{abab} {aabb}
10) Pumping lemma is a
powerful tool for providing certain languages non-regular
powerful tool for providing certain languages context sensitive
Both a and b
None of these
11) In GNF grammar is required in the form of
aα
Both a and b None of these
12) The is accepted unrestricted grammar.
TM PDA
DFA None of these
13) In PDA one situation has only one transition then it is known
as
TM DPDA
NPDA Stack
14) TM is more powerful than PDA.
True False
2. Answer the following (Any four). 8
Let R Find R*.
Define
Regular Expression
Language
Find language for the following regular expression.
ab* ab*
00(0
State difference between Moore and Mealy machine.
How many ways PDA accept language Give names.
Write note on (Any two). 6
Construct Mealy machine for decrement of binary number 1.
Explain notations used in CFG.
Show that
3. Answer the following (Any Two). 8
Find a deterministic acceptor equivalent to M q1,
q0
Δ A B
q0 q0, q1 q2
q1 q0 q1
q2 q0, q1
Convert the following right linear grammar to equivalent left linear
grammar.
S→ 0A 1B
A→ 0C 1A 0
B→ 1B 1A 0 1A 1
C→ a
Design a PDA to check whether a given string over ends in
abb.
Write note on (any one). 6
What is pumping lemma Using pumping lemma check
is regular or not.
Check whether the following grammar is ambiguous or not if ambiguity
found remove the ambiguity and rewrite an equivalent grammar
S->iCtS iCtSeS|a,
4. Answer the following (Any Two). 10
Construct F.A. equivalent to R.E.
Find CNF for the following grammar
A*A
Construct PDA that accepts the language generated by CFG.
Answer the following (any one). 4
Construct Turing Machine for checking well formdness of
parenthesis.
Construct DFA for find out given number is divisible by 3.
5. Answer the following (any two). 14
Design TM for L {anbn|n
Construct RE for following DFA by using Arden's theorem.
Explain simplification of grammar.
theory of computer science (Paper IV)
Day and Date Thursday, 22-11-2018 Total Marks 70
Time 2.30 p.m. to 5.00 p.m.
Instructions All questions are compulsory.
Figures to the right indicate full marks.
1. Choose correct alternatives. 14
All possible subset of set is known as
sub set power set
super set None of these
Proper prefix of the string abc
The empty string is denoted by
ε
Both a and b None of these
Function which mapping one to one from input to output such function is
known as function.
Machine State
Both a and b None of these
Push Down Automata has tuples.
4 5 6 7
Number of states requires accepting string ends with 10.
3 2
1 can't be represented
Set P
NFA is more powerful than DFA.
True False
A finite automata with output has final states.
True False
Regular expression denotes the set
{abab} {aabb}
10) Pumping lemma is a
powerful tool for providing certain languages non-regular
powerful tool for providing certain languages context sensitive
Both a and b
None of these
11) In GNF grammar is required in the form of
aα
Both a and b None of these
12) The is accepted unrestricted grammar.
TM PDA
DFA None of these
13) In PDA one situation has only one transition then it is known
as
TM DPDA
NPDA Stack
14) TM is more powerful than PDA.
True False
2. Answer the following (Any four). 8
Let R Find R*.
Define
Regular Expression
Language
Find language for the following regular expression.
ab* ab*
00(0
State difference between Moore and Mealy machine.
How many ways PDA accept language Give names.
Write note on (Any two). 6
Construct Mealy machine for decrement of binary number 1.
Explain notations used in CFG.
Show that
3. Answer the following (Any Two). 8
Find a deterministic acceptor equivalent to M q1,
q0
Δ A B
q0 q0, q1 q2
q1 q0 q1
q2 q0, q1
Convert the following right linear grammar to equivalent left linear
grammar.
S→ 0A 1B
A→ 0C 1A 0
B→ 1B 1A 0 1A 1
C→ a
Design a PDA to check whether a given string over ends in
abb.
Write note on (any one). 6
What is pumping lemma Using pumping lemma check
is regular or not.
Check whether the following grammar is ambiguous or not if ambiguity
found remove the ambiguity and rewrite an equivalent grammar
S->iCtS iCtSeS|a,
4. Answer the following (Any Two). 10
Construct F.A. equivalent to R.E.
Find CNF for the following grammar
A*A
Construct PDA that accepts the language generated by CFG.
Answer the following (any one). 4
Construct Turing Machine for checking well formdness of
parenthesis.
Construct DFA for find out given number is divisible by 3.
5. Answer the following (any two). 14
Design TM for L {anbn|n
Construct RE for following DFA by using Arden's theorem.
Explain simplification of grammar.
Other Question Papers
Subjects
- advanced java (paper – iii)
- advanced microprocessor
- compiler construction (paper – iv)
- computer graphics
- core java (old cgpa) (paper – iii)
- data communication and networking – i
- data communication and networking – ii (paper – i)
- data communications and networking – i (paper – i)
- data structures (paper – iv)
- data structures algorithms enginering – ii
- database management system – i (paper – ii)
- database management system – ii (paper – ii)
- dbms using oracle
- descriptive statistics – i
- descriptive statistics – ii
- digital electronics – i
- digital electronics and microprocesor – ii
- discrete structure
- embedded system – i
- embedded system – ii (paper – v)
- english (compulsory) (new) (cbcs)
- fundamental of computer
- golden petals
- introduction to programming using c – ii (paper – iii)
- introduction to web designing (paper – ii)
- linear electronics – i
- linear electronics – ii
- linux operating system (new)
- literary quest
- mathematical algebra
- mathematics(numerical methods)
- microprocesor – ii
- object oriented programming using c++
- object oriented programming using java (paper – i)
- on track – english skills for success
- oop using c++ – ii
- operating system
- operating system – ii (paper – i)
- operations research
- organization of pc – ii
- peripherals and interfacing – ii
- pr obabili ty theory – ii
- probability theory – i (paper – ix)
- programming using “c”
- python – i (paper – v)
- software engineering
- software enginering – ii
- theory of computer science
- theory of computer science (paper – iv)
- visual programming – i
- visual programming and aplication software – i (old)
- visual programming and aplication software – ii(paper – vi)
- web technology and e-commerce – i
- web technology and e-commerce – i (paper – v)
- web technology and e-commerce – ii (paper – v)