Scribd Logo
Upload

Welcome to Scribd!

  • 85 views

    Toc

    Uploaded by

    Akhil Gupta
    The document discusses theoretical computer science concepts including sets, strings, formal languages, grammars, automata and Turing machines. It contains 5 questions with multiple parts each related to formal languages and automata theory.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Toc

    Uploaded by

    Akhil Gupta
    85 views4 pages
    The document discusses theoretical computer science concepts including sets, strings, formal languages, grammars, automata and Turing machines. It contains 5 questions with multiple parts each related to formal languages and automata theory.

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses theoretical computer science concepts including sets, strings, formal languages, grammars, automata and Turing machines. It contains 5 questions with multiple parts each related to formal languages and automata theory.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    85 views4 pages

    Toc

    Uploaded by

    Akhil Gupta
    The document discusses theoretical computer science concepts including sets, strings, formal languages, grammars, automata and Turing machines. It contains 5 questions with multiple parts each related to formal languages and automata theory.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Total No.

    of Questions : 5]

    SEAT No. : [Total No. of Pages : 4

    P868

    [4140] - 202 M.C.A. Science Faculty COMPUTER SCIENCE CS - 202 : Theoretical Computer Science (2008 Pattern) (Sem. - II)
    Time : 3 Hours] Instructions to the candidates:
    1) 2) 3) All questions are compulsory. Figures to the right indicate full marks. Neat diagrams must be drawn wherever necessary.

    [Max. Marks : 80

    Q1) Attempt all of following a) b) c) d) List any four properties of sets. Define Suffix and list all proper suffixes for string "abcd".

    [8 2 = 16]

    Define tuples for DFA and write the condition for string acceptance in FA. Describe the language in English and give the language set for the following regular expression. a (a + b)* b + b (a + b)* a

    e) f)

    Define Nullable Symbol and give one example. Write a language for CFG S o C5D D5C language. and define the set for the

    g) h)

    Prove that the relation "=" is equivalence relation on set S. Define Halting Problem of Turing Machine. Represent the halting set. [4 4 = 16]

    Q2) Attempt any 4 of following: a)

    Construct the DFA to accept all decimal numbers divisible by 3.

    P.T.O.

    b)

    Convert the following Moore machine equivalent to Melay machine State q0 q1 q2 d a q1 q1 q1 b q2 q1 q0 0 1 0 l

    c)

    Construct the CFG for the following languages i) ii) L = a*b* L = ab*

    iii) L = (baa + abb)* iv) L = {an bmcn| n_ > 0, m >0} d) e) Write a short note on Chmoskey hierarchy of languages. Convert the following DFA to its equivalent NFA where M = ({q0, q1, q2, q3}, {0, 1, 2}, d, q0, {q2, q3}) State q0 q1 q2 q3 d 0 {q0, q3} {q1, q3} {q2, q3} f 1 {q1, q3} {q2, q3} {q2, q3} f 2 q0 q2 f f [4 4 = 16]

    Q3) Attempt any 4 of following. a)

    Convert the following CFG, G = ({S, A, B}, {a, b}, P, S) to its equivalent CNF-P : S aAab | Aba A aS | bB B ASb | a

    b) c)

    Construct the PDA to accept well formedness of parenthesis over ({, (,[,],),})* Convert the following NFA with e - transition to equivalent DAF where M = ({q0, q1, q2, q3, q4, q5}, {0, 1,}, d, q0, {q5})

    [4140]-202

    d: State q0 q1 q2 q3 q4 q5 d) e) d 0 f q2 f f f 1 f f q3 f q5

    Construct the Moore machine to give output A if the string ends in 'pqr', 'B' if string ends in 'prp', otherwise output will be C. Construct NFA for the regular language (a + b*)* + a* bb* [4 4 = 16]

    Q4) Attempt any 4 of following: a) b) c)

    Prove that the regular languages are closed under Homomorphism. Construct the Turing machine which will replace every occurrence of a substring 11 if any, by keeping everything else intact over {0,1} Convert the following CFG G = ({S,A,B,C}, {a, b}, P, S) to equivalent GNF P : S ABC Aa|b B Bb | aa C aC | cC | ba Convert the following CFG G = ({S,A,B}, {0, 1}, P, S) to equivalent PDA P : S 0A1 A 0A1 | B B 1B| 1 Prove that the following DFA can not be minimized.

    d)

    e)

    [4140]-202

    Q5) Attempt any 4 of following: a) b) c) d)

    [4 4 = 16]

    Prove that the language L = {an bn | n >=1} is not regular using pumping lemma. Prove that the CFS are closed under concatenation. Construct the Turing machine to multiply two unary numbers. Describe the language represented by following regular expressions i) ii) R = (0+1)*0 R = (1+01)*(0+01)*

    e)

    Convert the following PDA to its equivalent CFG M = ({q0, q1}, {a,b}, {Z0, Z1}, d, q0, Z0, f) d: d (q0, b, Z0) (q0, ZZ0) d (q0, e, Z0) (q0, e) d (q1, a, Z0) (q0, Z0) d (q0, b, Z) (q0, ZZ) d (q0, a, Z) (q1, Z) d (q1, b, Z) (q1, e)

    nnn

    [4140]-202

    You might also like