Exam Details
| Subject | theory of computer science | |
| 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 (New CBCS) Examination, 2018
Theory of Computer Science (Paper III)
Day and Date Tuesday, 20-11-2018 Total Marks 70
Time 2.30 p.m. to 5.00 p.m.
1. Multiple Choice Questions 14
If S and R then R is said to
be
Reflexive Transitive
Symmetric Reflexive and Transitive
Every NFA with epsilon-moves can be converted into
DFA NFA without epsilon-moves
Both a and b None of these
If L 00, 01, 10, 11, ....... then r
0
The productions required to generate the language L aa, aaa, ....}
is
The is mathematical model of machine or computer.
FA Turing Machine
PDA Regular Expression
Turing machine is language recognizer of language.
Context Free Context sensitive
Phase structured All of the above
CFL is closed under union, concatenation and
operation.
set difference kleene star
both a and b none of these
If A then power set of set A contains
number of elements.
5 10 32 31
Mealy machine and Moore machine represents
FA with output FA without output
Both a and b None of these
10) Pumping Lemma is used to prove that language is
Regular Not regular
Context free Context sensitive
11) is capable of performing computations on inputs and
producing a new result.
FA FA with output
NFA Turing machine
12) all these productions are in the
CNF GNF
both a and b KNF
13) In case of we can move from one state to another but without
reading any input symbol.
NFA without €-moves NFA with €-moves
DFA None of these
14) Proper suffixes of the string "pqr" are
qr, pr}
qr} qr, pqr}
2. Answer the following (any four) 8
Define
set language
Construct DFA for the following
L ends with aab}
Describe in English the language represented by following expression.
Give a context free grammar for the following language.
0(0
Define PDA.
W rite notes on (any two) 6
Find the transitive closure and the symmetric closure of the relation.
Construct FSM for checking number is divisible by 2.
Design Turing machine which accept string ending with ab over Σ b}.
3. Answer the following (any two) 8
Design Mealy machine for complement.
For the grammar given below.
T
a b
Give the derivation of also draws the parse tree for the same
expression.
Construct FA equivalent to RE.
Answer the following (any one) 6
Consider the following NFA with ε-moves.
into DFA.
ε a b c
→ p p q r
q p q r
q r p
Write a note on Simplification of grammars.
4. Answer the following (any two) 10
Find a grammar in CNF equivalent to grammar
Design PDA for well formedness of parenthesis.
Design DFA over an Σ which accept the language that start
and end with different symbol.
Answer the following (any one) 4
Find regular expression for following
Design a Turing machine to check whether a string over
contains equal number of s nd b's.
5. Answer the following (any two) 14
Check the following grammar is ambiguous or not if found the remove it.
For string aaabbabbba.
Draw a transition diagram for a Turing machine accepting the following
language.
L {ai bj|I
Give the GNF for following CFG.
Theory of Computer Science (Paper III)
Day and Date Tuesday, 20-11-2018 Total Marks 70
Time 2.30 p.m. to 5.00 p.m.
1. Multiple Choice Questions 14
If S and R then R is said to
be
Reflexive Transitive
Symmetric Reflexive and Transitive
Every NFA with epsilon-moves can be converted into
DFA NFA without epsilon-moves
Both a and b None of these
If L 00, 01, 10, 11, ....... then r
0
The productions required to generate the language L aa, aaa, ....}
is
The is mathematical model of machine or computer.
FA Turing Machine
PDA Regular Expression
Turing machine is language recognizer of language.
Context Free Context sensitive
Phase structured All of the above
CFL is closed under union, concatenation and
operation.
set difference kleene star
both a and b none of these
If A then power set of set A contains
number of elements.
5 10 32 31
Mealy machine and Moore machine represents
FA with output FA without output
Both a and b None of these
10) Pumping Lemma is used to prove that language is
Regular Not regular
Context free Context sensitive
11) is capable of performing computations on inputs and
producing a new result.
FA FA with output
NFA Turing machine
12) all these productions are in the
CNF GNF
both a and b KNF
13) In case of we can move from one state to another but without
reading any input symbol.
NFA without €-moves NFA with €-moves
DFA None of these
14) Proper suffixes of the string "pqr" are
qr, pr}
qr} qr, pqr}
2. Answer the following (any four) 8
Define
set language
Construct DFA for the following
L ends with aab}
Describe in English the language represented by following expression.
Give a context free grammar for the following language.
0(0
Define PDA.
W rite notes on (any two) 6
Find the transitive closure and the symmetric closure of the relation.
Construct FSM for checking number is divisible by 2.
Design Turing machine which accept string ending with ab over Σ b}.
3. Answer the following (any two) 8
Design Mealy machine for complement.
For the grammar given below.
T
a b
Give the derivation of also draws the parse tree for the same
expression.
Construct FA equivalent to RE.
Answer the following (any one) 6
Consider the following NFA with ε-moves.
into DFA.
ε a b c
→ p p q r
q p q r
q r p
Write a note on Simplification of grammars.
4. Answer the following (any two) 10
Find a grammar in CNF equivalent to grammar
Design PDA for well formedness of parenthesis.
Design DFA over an Σ which accept the language that start
and end with different symbol.
Answer the following (any one) 4
Find regular expression for following
Design a Turing machine to check whether a string over
contains equal number of s nd b's.
5. Answer the following (any two) 14
Check the following grammar is ambiguous or not if found the remove it.
For string aaabbabbba.
Draw a transition diagram for a Turing machine accepting the following
language.
L {ai bj|I
Give the GNF for following CFG.
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)