University of Sargodha MS 1" Term Examination 2014 Subject: Computer Science Paper: Advance Theory of Computation (CS-5111) Time Allowed: 3 Hours

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)

ustadni.com

VI.

vii.

vili.

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.

Subjective Part

Q.No2 [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.

L= (ba|1>0}

Ø.No3 (8+8]

a) Show that the collection of Turing-recognizable languages is closed under the operation of union.

b) Prove that halting problem is undecideable.

.No4 (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 1s }

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).

a a re la maping reil to re hother words, show that no computatile function

3) Le 4(M) /M is a DFA which doced the fation of compierment.

b) Give context-free grammars generating the following languages.

The set of strings over the alphabet (a,b) with more a's than b's

il.

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)= {xz|xyz € A where x,2

€≥*, y€2 ). 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