B.E. Computers, IT Notes/Solved Question papers Maharashtra, Mumbai

Showing posts with label TCS. Show all posts

Saturday, June 14, 2014

THEORY OF COMPUTER SCIENCE (TCS) MAY 2012 COMPUTER SCIENCE SEMESTER 5

Con. 4554-12.                                                                         GN-8579
                                                         (3 Hours)                           [Total Marks : 100]

N.B.: 1) Question number 1 is compulsory.
        2) Attempt any four questions out of remaining six questions.
        3) Assumptions made should be clearly stated.
        4) Figures to the right indicate full marks.
        5) Assume suitable data wherever required but justify the same.

Q.1. a.	State and prove the Pumping Lemma for Regular Language.	(05)
b.	Explain the different techniques for Turing Machine Construction.	(05)
c.	Compare and Contrast Moore and Mealy Machine.	(05)
d.	Prove that it is undecidable whether Context free grammar is ambiguous.	(05)
Q.2. a.	Write a regular expression for the following languages.	(10)
	i. The set of all the strings such that the number of 0's is odd.
	ii. The set of all the string that do not contain 1101.
b.	Convert the following NFA to DFA	(10)
	p is the initial state and r and s are the final state
Q.3. a.	Show that every regular language is context free language	(10)
	Hint: Construct a CFG by induction on the number of operators in the
	regular expression.
b.	A Palindrome is a string that equals its own reverse,	(10)
	such as 0110 or 1011101. Use the pumping lemma to show that
	the set of palindromes is not a regular language.
Q.4. a.	Design a PDA to accept each of the following languages	(10)

b.	Convert the grammar	(10)

	S-> 0AA
	A -> OS\|1S\|0
	to a PDA that accepts the same language by empty stack.
Q.5. a.	Begin with the grammar:	(14)
	S-> ABC\|BaB
	A-> aA\|BaC\|aaa
	B-> bBb\|a\|D
	C-> CA\|AC
	D-> C
	i. Eliminate ϵ Productions.
	ii. Eliminate any unit production in the resulting grammar.
	iii. Eliminate any useless symbols in the resulting grammar.
	iv. Put the resulting grammar into Chomsky Normal Form.
b.	prove that L={an \| n is prime} is not context free.	(06)
Q.6. a.	Design a Turing Machine for the following language.	(10)
	"set of all the string of balanced parentheses".
b.	Convert the following grammar into Greibach Normal Form.	(10)
	S→ AB1 \| 0
	A→ 00A \| B
	B→ 1A1
Q.7. a.	Myhill-Nerode Theorm.	(05)
b.	Post Correspondence Problem.	(05)
c.	Universal Turing Machine.	(05)
d.	The Classes P and NP.	(05)

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2011 COMPUTER SCIENCE SEMESTER 5

(3 Hours) [Total Marks:-100]

1. (a) Design finite state machine which accepts exactly the two strings baa and ab. [5 Marks]
(b) Convert the following NFA to a DFA. [5 Marks]

(c) Convert the following regular expression to NFA with - transactions:- [5 Marks]
R = (1(00)*1 + 0 1*0)*
(d) Write a short note on Ambiguity Resolution. [5 Marks]

2. (a) Obtain DFA to accept the strings which contains exactly three a's over ∑ ={a,b} [8 Marks]
(b) Give Mealy and Moore machine to change each occurrence of substring 120 to 121
over ∑={0,1,2} [10 Marks]
(c) Give the statement of Pumping Lemma for regular Languages. [2 Marks]

3. (a) Minimize the following DFA, where is the q0 start state and q3 and q5 are final
states:- [10 Marks]

(b) Using Pumping Lemma, show that following grammars are not regular:- [10 Marks]

(i)

(ii)

4. (a) Consider the grammar:- [10 Marks]

S -> OB|1A

A -> O|OS|1AA

B -> 1|1S|OBB

For the string 00110101 find the follwoing:-

(i) Leftmost Derivation

(ii) Rightmost derivation

(iii) Parse tree

(b) Convert the follwoing grammar into CNF :- [10 Marks]

S -> ASB|ϵ

A -> aAS|a

B -> SbS|A|bb

5. (a) Convert the following grammar in GNF :- [8 Marks]

S -> AA | 0

A -> SS | 1

(b) Construct PDA for the following language: - [8 Marks]

6. (a) Define PDA and construct PDA grammar:- [10 Marks]

E -> E+E|E-E|(E)|id

(b) Design Turing machine for recognising the following language: - [10 Marks]

(i)

(ii)

7. Write short notes on any four of the following:- [20 Marks]

(a) Chomsky hierarchy

(b) Post Correspondence Problem

(d) Halting Problem

(e) Closure properties of context free language.

Friday, June 13, 2014

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2012 COMPUTER SCIENCE SEMESTER 5

Con. 7632-12. KR-5348
(3 Hours) [Total Marks : 100]

N.B. : (1) Question No. 1 is compulsory.
(2) Attempt any four questions from remaining six questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.

1. (a)	What is finite automation ? Give the finite automation M accepting (a,b)*(baaa).	5
(b)	Explain Chomsky Hierarchy with languages used, forms of productions in grammars	5
	and accepting device.
(c)	Differentiate Moore and Mealy machine.	5
(d)	Give and explain ambiguous context free language.	5
2. (a)	Design finite state machine to add 2 binary numbers of equal length.	10
(b)	Give the rules for defining languages associated with any regular expression :	10
	Let L1 = all words beginning with a
	L2 = all words ending with a
	what is L1 intersection L2 ?
3. (a)	Give the statement for pumping Lemma for regular languages.	2
(b)	Construct an NFA-^ for -
	(i) (00 + 1) * (10)*
	(ii) ((0 +1)10 + (00)(11))
(c)	Let G be the grammar
	S → aB \| bA
	A → a \| aS \| bAA
	B → b \| bS \| aBB
	Find the leftmost derivation, right most derivation and parse tree for the string
	"bbaaabbaba".
4. (a)	What is TM ? Give the power of TM over FSM. Explain undecidebility and	10
	incompleteness in Turing machine.
(b)	Explain PDA and power of PDM. Also design the NPDA for given-	10
	CFG
	S → aAA
	A → bS
	A → aS
	S → a
5. (a)	Explain basic Complexity classes.	6
(b)	Define NP-hard and NP-complete languages.	4
(c)	Using pumping lemma, check whether an bn is regular or not.	10
6. (a)	How regular expression is converted to DFA ? Explain all rules with example.	10
(b)	Construct a PDA accepting the language of Palindromes.	10
7.	Write short notes on (any four) :-	20
	(a) Myhill Nerode Theorem
	(b) Universal TM
	(c) Rice Theorem
	(d) Closure properly and decision algorithm for CFL
	(e) Application areas of RE, FA, PDA, CFG, TM.

THEORY OF COMPUTER SCIENCE (TCS) MAY 2011 COMPUTER SCIENCE SEMESTER 5

(3 Hours) [Total Marks:- 100]

1. (a) Differentiate between:-
(i) NFA and DFA
(ii) Moore and Mealy machines. [5 Marks]
(b) Design a Mealy Machines. [5 Marks]

2. (a) Design a DFA to accept the following languages over the alphabet {0,1} [10 Marks]
(i) {W | W starts with zero and has odd length or starts with one has even length}
(ii) {W|every odd position of w is 1}
(b) Find a minimum state finite automata equivalent to the following automata :- [10 Marks]

3. (a) Give and explain the formal statement of Pumping Lemma for regular languages and use it to
prove that the following language is not regular : - [10 Marks]

(b) Convert the following NFA with epsilon moves to a minimum state DFA accepting the
same language:- [10 Marks]

4. (a) Design a PDA for the language [10 Marks]

(b) Design a PDA for the following grammar and test whether is in the language defined by that
PDA. [10 Marks]
S -> 0BB
B -> 0S | 1S | 0

5. (a) Reduce the following grammars to GNF [10 Marks]
(i) S -> AB
A -> BSB | BB| b
(ii) B aAB | a [5 Marks]
S -> AA | 1
A -> SS | 1
(b) Convert the following grammars to CNF [10 Marks]
A -> aBb | bBa
B -> aB | bB | ε

6. (a) Design a Turing Machine to accept the language [10 Marks]

(b) Design a Turing Machine that computes a function f(m,n) = m+n for the addition of 2

integers. [10 Marks]

7. Write short notes on (any three) :- [20 Marks]

(a) Halting problem

(b) Post Correspondence Problem

(d) Intractable Problems

(e) Greibach Theorem.

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2010 COMPUTER SCIENCE SEMESTER 5

Con. 5564-10. (REVISED COURSE) GT-6708.

(3 Hours) [Total Marks:100]

N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four questions from remaining six questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.

Q.1 (a) Explain different types of machines and states at least one application of each. [10 Marks]
(b) Let G be the grammar. Find the leftmost derivation, rightmost derivation and parse tree for
the string 00110101 [10 Marks]
G: S -> 0B|1A
A -> 0|0S|1AA
B -> 1|1S|0BB

Q.2 (a) Design a DFA to accept [10 Marks]
(i) a set of all strings with odd number of ones followed b even number of zeros.
(ii) a set of all strings with which begin and end with different letters ∑= {x,y,z}
(b) What is a regular expression? Give formal definition of a regular expression. Design a
DFA corresponding to the regular expression (a+b) * aba(a+b)*. [10 Marks]

Q.3 (a) Design a Moore and Mealy machine to convert each occurrence of a substring abb by
aba. [10 Marks]
(b) Convert the following NFA with epsilon moves to an NFA without epsilon moves and then
to a DFA. [10 Marks]

Q.4 (a) Using Pumping Lemma prove that the following languages are not regular. [10 Marks]
(i)

(ii)

(b) Design a turing machine to generate the languages given by a regular expression
0(0+1)*11. [10 Marks]

Q.5 (a) List and explain decision properties of regular languages. Explain the test for checking
emptiness of a regular language. [10 Marks]
(b) State Arden's theorem and use it to construct a regular expression correspondence to the
following automata. [10 Marks]

(b) Explain the rules for simplification of a context free grammar. [10 Marks]

Q.7 Write short notes on(any three):- [20 Marks]
(a) Variants of a Turing Machine
(b) Post Correspondence Problem
(c) Chomsky Hierarchy
(d) Intractable Problem
(e) Recursive and recursively enumerable languages.

Thursday, June 12, 2014

THEORY OF COMPUTER SCIENCE (TCS) MAY 2010 COMPUTER SCIENCE SEMESTER 5

Con.3719-10 (REVISED COURSE) AN-4228

(3 Hours) [Total Marks:-100]

N.B: (1) Question No.1 is compulsory.
(2) Attempt any four questions from the remaining questions.

1. (a) Define DFA and state applications of Finite Automata in brief. [5 Marks]
(b) Obtain a grammer to generate the language

(d) Differentiate deterministic Push Down Automata and Non-deterministic Push Down
Automata. [5 Marks]

2. (a) (i) Obtain DFA to accept string's of a a's and b's with even no of a's and even no of a's and
even no. of b's. [10 Marks]
(ii) Obtain a regular expression such that L(R) = {W |W with atleast three consecutive's zeros.
(b) Give Mealy and Moore machine for input ends in 110, output should be y, otherwise output
should be z. [10 Marks]

3. (a) Design PDA for the following languages. [10 Marks]
L(M) = {WCwR} Wε{a,b} where wR is reverse of W and C is constant. [10 Marks]
(b) For the grammar
S -> aABC
A -> aB/a
B -> bA/b
C -> a
Obtain the corresponding PDA.

4. (a) Using Pumping Lemma theorem, show that following grammars are not regular:- [10 Marks]
(i)

(ii)

(b) Construct reduced DFA for language represented by [10 Marks]
(ab/ba)*aa(ab/ba)

5. (a) Convert the following grammar in Chomsky Normal form [10 Marks]
S -> ASB/ε
B -> Sbs/A/bb
A -> aAS/a
(b) Show that the following grammar is ambiguous [10 Marks]
S -> aSbs
B -> bSaS
A ->

6. (a) Design TM that replaces all occurrences of "111" by "101" from sequence of 0's
and 1's. [10 Marks]
(b) Define post correspondence problem and prove that PCP with two lists x = {b,bab3,ba} and
y = {b3, ba,a} have a solution. [10 Marks]

7. (a) Minimize the following DFA, where q3 and q5 are final states [10 Marks]

(b) Write short notes on:- [20 Marks]
(i) Universal Turing Machine
(ii) P & NP problems.

THEORY OF COMPUTER SCIENCE (TCS) MAY 2013 COMPUTER SCIENCE SEMESTER 5

Con. 6972-13. GS-9099
(3 Hours) [Total Marks : 100]

N.B. (1) Question No. 1 is compulsory.
(2) Attempt any four questions from remaining six questions.
(3) Draw suitable diagrams wherever necessary.
(4) Assume suitable data, if necessary.
(5) Maximum weightage is given to technical notations.

1. (a)	Define the following terms :-	5
	(i) Undecidability
	(ii) Unrestricted grammar
	(iii) Pumping lemma.
(b)	Define TM and Give its variants.	5
(c)	Explain Chomsky hierarchy for formal languages.	5
(d)	Give the closure properties of regular languages.	5
2. (a)	(i) What is ambiguous CFG ? Give one example of ambiguous CFG.	5
	(ii) What is Myhill-Nerode theorem ? Explain necessity of it.	5
(b)	Let G be the grammar, find the leftmost derivation , right most derivation and parse	10
	tree for the string 00110101
	S → OB / 1A
	A → O/OS/1AA
	B → 1/1S/OBB
3. (a)	Explain CNF and GNF with example.	10
(b)	Give the formal definition of RE and design a DFA corresponding to the regular	5
	expression
	(a+b) * aba (a+b)*
(c)	Using pumping lemma prove that the following language is regular or not	5

4. (a)	Write NFA for accepting the following RE	10
	(a+bb)* + ϵ)
(b)	Explain DPDA and NPDA with languages of them.	10
5. (a)	Find the languages defined by the following grammar :	10
	(i) S → OA/ IC
	A → OS / IB / ϵ
	B → 1A / OC
	C → OB / 1S
	(ii) S → OA / IC
	A → OS / IB
	B → OC / IA / ϵ
	C → OB / IS
(b)	Construct the PDA accepting following language	10

6. (a)	Differentiate between Moore and Mealy machine with proper example and usage	10
	Cary out conversion of Moore MIC to Mealy MIC.
(b)	Design a Turing machine to accept the language	10

7. Write short notes on any four :- 20
(a) Recursive and recursively enumerable languages
(b) Intractable problems
(c) Simplification of CFGs
(d) Decision properties of regular languages
(e) Rice's theorem.

Wednesday, June 11, 2014

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2013 COMPUTER SCIENCE SEMESTER 5

Con. 7047-13. LJ - 11377
(3 Hours) [Total Marks : 100]

N. B. : (1) Question No. 1 is compulsory.
(2) Attempt any four questions from remaining six question.
(3) Assumptions made should be clearly stated.
(4) Figure to the right indicate full marks.

1. (a)	Define with examples Moore and Mealy machine	5
(b)	Find the equivalent DFA accepting the regular language defined by right linear	5
	grammer given as:-
	S → aA\|bB
	A → aA\|bC\|a
	B → aB\|b
	C → bB
(c)	State and prove pumping Lemma theorm for regular language.	5
(d)	Differentiate between Deterministic PDA and Non-deterministic PDA.	5
2. (a)	Design a finite state machine to determine whether a ternary number base 3 is	10
	divisible by 5. [Hint : ∑ = {0,1,2}]
(b)	Design a Mealy machone for the language {0+1)* (00+11) and convert it to a	10
	Moore machine.
3. (a)	Convert the following NFA with € moves to DFA :-	10

(b)	Let G be the grammer. G = {(S, X), {a,b}, P, S} where productions are :-	10
	S → aSX\|b
	X → Xb\|a
	Find:- {i} Leftmost derivation.{ii} Rightmost derivation and
	{iii} Parse tree for the string "aababa".
4. (a)	Design turing machine for the language L={anbn\|n>=1	10
(b)	Design a turing machine to compare the binary number m and n such that if	10
5. (a)	(m>n) output is G, if *(m<n) output is L and when (m=N) output is E. List and explain decision properties of regular language.	10
	Explain the test for checking emptiness of a regular language.
(b)	Construct left linear and right linear grammer for the regular expression :-	10
	(((01 + 10)* 11)00)
6. (a)	Construct a PDA equivalent to following grammar:-	10
	S → oBB
	B → OS\|IS\|O
	and show the acceptance of 010 by the PDA.
(b)	Reduce the folowing grammer to Greibach Normal form.	5
	(i) S → AB
	A → BSB\|BB\|b
	B → a
	(ii) S → 01S\|01	5
	S → 10S\|10
	S → 00\|˄
7.	Write short notes on (any four) :-	20
	(a) Post Correspondence Problem
	(b) Chomsky Hierarchy
	(c) Universal turing machine
	(d) Recursive and Recursively emurable language
	(e) Classes of complexity

THEORY OF COMPUTER SCIENCE (TCS) DECEMBER 2009 COMPUTER SCIENCE SEMESTER 5

Con.5503-09. (REVISED COURSE) SP-8562

(3 Hours) [Total Marks:100]

Note:- (1) Question No.1 is compulsory
(2) Attempt any four questions from remaining six questions.
(3) Figures to the right indicate full marks given to the questions.
(4) Assume suitable data, if necessary.

1. (a) Distinguish between NFA and DFA. [4 Marks]
(b) Design Finite Automata from 1(0/1)*0 Regular Expression. [5 Marks]
(c) Explain CNF and GNF with example. [5 Marks]
(d) Explain classes of Complexity with example. [6 Marks]

2. (a) Design a Moore and Mealy Machine to convert substring aba into abb. [10 Marks]
(b) Construct DFA accepting the following language. [10 Marks]
(i) Strings ending with 110 or 111.
(ii) String containing 010 as a substring.

3. (a) (b) Let G be the grammar [10 Marks]
S -> aB|bA
A -> a|aS|bAA
B -> b|bS|aBB
Find leftmost derivation, rightmost derivation and parse tree for the string "bbaaabbaba".

(b) Design of PDA for the following CFG: [10 Marks]
S -> (S) | SS|

4. (a) State and explain pumping Lemma for regular languages. [10 Marks]
Using Pumping Lemma, show that the following grammars are not regular.
(i) L= {1n| n is prime number}
(ii) L= {0n 10n|n>0}
(b) Design a TM to subtract two numbers (e.g m and n are two integers and m-n is to be
evaluated ) assume m>n. [10 Marks]

5. (a) Construct NFA from (0+1)*(00+11) and convert into minimized DFA. [10 Marks]
(b) Write CFG for language having numbers of a's greater than number of b's and Design a PDA for
the same. [10 Marks]

6. (a) Design a TM to accept language {0n1n|n>0} [10 Marks]
(b) Explain decision properties for regular languages. [10 Marks]

7. Write short notes on (any four):- [20 Marks]
(a) Variants of TM
(b) Deterministic Pushdown Automata
(c) Recursive and Recursively Enumerated Languages.
(d) Complements of languages in NP.
(e) Chomsky Hierarchy