and 4 others joined a min ago.
0
1.3kviews
Theory of Computer Science Question Paper - Jun 19 - Computer Engineering (Semester 5) - Mumbai University (MU)
1 Answer
0
10views
written 4.8 years ago by
teamques10
★ 64k
|
Theory of Computer Science - Jun 19
Computer Engineering (Semester 5)
Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.
1.a.
Differentiate DFA and NFA.
(5 marks)
00
1.b.
Design a DFA to accept string of 0‟s and 1‟s ending with the string 100.
(5 marks)
00
1.c.
Explain the applications of Regular Expressions.
(5 marks)
00
1.d.
What are Recursive and Recursively Enumerable Languages?
(5 marks)
00
2.a.
Design NFA for recognizing the strings that end in “aa” over $\Sigma = \{ a , b \}$ & convert above NFA to DFA.
(10 marks)
00
2.b.
Design moore m/c for following:-
If input ends in '101' then output should be A, if input ends in '110' output should be B, otherwise output should be C and convert it into mealy m/c.
(10 marks)
00
3.a.
Obtain a regular expression for the FA shown below:
(10 marks)
00
3.b.
Explain the types of Turing machine in detail.
(10 marks)
00
4.a.
Design a Turing machine that computes a function f(m,n)=m+n i.e. addition of two integers.
(10 marks)
00
4.b.
State and explain pumping Lemma for Context Free Languages. Find out whether the language $\mathrm{L}=\left\{\mathrm{x}^{\mathrm{n}} \mathrm{y}^{\mathrm{n}} \mathrm{z}^{\mathrm{n}} | \mathrm{n} \geq 1\right\}$ is context free or not.
(10 marks)
00
5.a.
Design PDA for the following language:
$\mathrm{L}(\mathrm{M})=\left\{\mathrm{wcw}^{\mathrm{R}} | \mathrm{w} \quad\{\mathrm{a}, \mathrm{b}\}^{*}\right\}$ where $w^{R}$ is reverse of w & c is a constant.
(10 marks)
00
$\mathrm{L}(\mathrm{M})=\left\{\mathrm{wcw}^{\mathrm{R}} | \mathrm{w} \quad\{\mathrm{a}, \mathrm{b}\}^{*}\right\}$ where $w^{R}$ is reverse of w & c is a constant.
5.b.
Convert the following Grammars to the Chomsky normal form (CNF).
$\mathrm{S} \rightarrow 0 \mathrm{A} 0|1 \mathrm{B} 1| \mathrm{BB}$
$\mathrm{A} \rightarrow \mathrm{C}$
$\mathrm{B} \rightarrow \mathrm{S} | \mathrm{A}$
$\mathrm{C} \rightarrow \mathrm{S} | \varepsilon$
(10 marks)
00
$\mathrm{S} \rightarrow 0 \mathrm{A} 0|1 \mathrm{B} 1| \mathrm{BB}$
$\mathrm{A} \rightarrow \mathrm{C}$
$\mathrm{B} \rightarrow \mathrm{S} | \mathrm{A}$
$\mathrm{C} \rightarrow \mathrm{S} | \varepsilon$
Write detailed note on any two.
6.a.
Post Correspondence Problem
(10 marks)
00
6.b.
Halting Problem.
(10 marks)
00
6.c.
Rice's Theorem.
(10 marks)
00
ADD COMMENT
EDIT
Please log in to add an answer.