5317- University of Sargodha MS 1" Term Examination 2014 Subject: Computer Science Paper: Advance Theory of Computation (CS-5111)
Discussion
Ask a question about this paper, or help someone else with theirs. Answers are emailed to whoever asked.
No questions yet — be the first to ask.
More Advance Theory of Computation papers
See all
Paper text
5317-
University of Sargodha
MS 1" Term Examination 2014
Subject: Computer Science Paper: Advance Theory of Computation (CS-5111)
Time Allowed: 3 Hours
Session: 2014-16 Spring
Maximum Marks: 80
Note:
Objective part is compulsory. Attempt any four questions from subjective part.
Objective Part
(2*8)
vii.
vili.
Every superset of a regular languaged legular
The class NP of the languages is closed under union
Set of all Turing decidable languages is recursive.
If Arreduces to language L, then L is undecided able.
The complement of a context free language is also context free.
ustadni.com
Subjective Part
QrNo2 (8+8]
a) Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank
** symbol on its second tape when it is run on input w. Formulate this problem as a language, and show
that it is undecidable.
b) Design a PDA for the following language.
= (b'a" i>0
Q.No3 18+8
a) Show that the collection of Turing-recognizable languages is closed under the operation of union.
b) Prove that halting problem is undecideable.
Q.N04 (4+4+4+4]
Design deterministic finite machines (DFAs) and write regular expressions for the following languages
over 2=(0, 1}.
a) {w |w contains atleast three Is !.
b) {w w is any string except 11 and 000}.
c) {w | every odd position of w is a 0).
d) {w | w contains atleast two Os and at most one 1}.
3) Show h
b) Give context-free grammars generating the following languages.
b) Give contest of srings aver the alpha be fallowing more as than be
ii. The complement of the language (a"b" | n> 0}
Q.No7 [10+6]
a) Let A be any language. Define DROP-OUT(A) to be the language containing all strings that can be
obtained by removing one symbol from a string in A. Thus, DROP-OUT(A)=(xzxyz € A where x,z.
€2*, y€Z ). Show that the class of regular languages is closed under the DROP-OUT operation.
b) Prove using pumping lemma that the given language is not regular.
{0"1"0"|m,n>0}
visit website: ustadni.com