Home /UOS — University of Sargodha /Main Campus /Advance Theory of Computation

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

5317- University of Sargodha MS 1" Term Examination 2014 Subject: Computer Science Paper: Advance Theory of Computation (CS-5111) — page 1

Discussion

Ask a question about this paper, or help someone else with theirs. Answers are emailed to whoever asked.

Your email is only used to send you replies and occasional Ustadni updates. It is never shown publicly.

Log in to post under your name

No questions yet — be the first to ask.

Need Paper? See all →

Need a paper or stuck on a question? Ask here — students reply and you get an email.

Ask about a paper
  • Ayesha Mustafa· 11 days ago

    BS ZOOLOGY first semester Animal diversity ZOOL 101 - university of Punjab 2025

    0 replies Reply →
  • Abubakar· 11 days ago

    Literary criticism

    1 reply Reply →
  • Guest· 12 days ago

    this paper consists of 60 marks but now we have 35 marks paper.

    1 reply Reply →
  • saira khalid· 1 month ago

    air past paper nhi h

    1 reply Reply →
Ad

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