Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    Toc Summer 2018

    Uploaded by

    Jayraj Rajput
    GTU PYQ SUMMER 2018

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Toc Summer 2018

    Uploaded by

    Jayraj Rajput
    7 views3 pages
    GTU PYQ SUMMER 2018

    Original Title

    TOC SUMMER 2018

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    GTU PYQ SUMMER 2018

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    7 views3 pages

    Toc Summer 2018

    Uploaded by

    Jayraj Rajput
    GTU PYQ SUMMER 2018

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    Seat No.: ________ Enrolment No.

    ___________
    GUJARAT TECHNOLOGICAL UNIVERSITY
    BE - SEMESTER–VI (NEW) - EXAMINATION – SUMMER 2018
    Subject Code:2160704 Date:03/05/2018
    Subject Name:Theory of Computation
    Time:10:30 AM to 01:00 PM Total Marks: 70
    Instructions:
    1. Attempt all questions.
    2. Make suitable assumptions wherever necessary.
    3. Figures to the right indicate full marks.

    Q.1 (a) Show that the CFG with productions 03


    S  a | Sa | bSS | SSb | SbS
    is ambiguous.
    (b) Define onto function. In each case, a relation on the set {1, 2, 3} is given. Of the 04
    three properties, reflexivity, symmetry, and transitivity, determine which ones the
    relation has. Give reasons.
    a. R = {(1, 3), (3, 1), (2, 2)}
    b. R = {(1, 1), (2, 2), (3, 3), (1, 2)}
    c. R = ϕ
    (c) Write Principle of Mathematical Induction. Prove that for every n ≥ 1, 07
    1
    ∑𝑛𝑖=1 = n / (n + 1)
    𝑖(𝑖 + 1)
    Q.2 (a) Explain Chomsky Hierarchy. 03
    (b) Convert the given Moore machine into Mealy machine. Draw state transition 04
    diagram of Mealy machine.
    Present Next State Output
    State 0 1
    p0 r q0 ɛ
    p1 r q0 1
    q0 p1 s0 0
    q1 p1 s0 1
    r q1 p1 0
    s0 s1 r 0
    s1 s1 r 1
    (c) Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. 07
    G: S  AaA | CA | BaB
    A  aaBa | CDA | aa | DC
    B  bB | bAB | bb | aS
    C  Ca | bC | D
    D  bD | ɛ
    ɛ represents null.
    OR
    (c) Define Context Free Grammar. Find context-free grammar for the language: L 07
    = {aibj | i < 2j}
    Q.3 (a) Show that the function f(x, y) = x + y is primitive recursive. 03
    (b) Explain Union Rule and Concatenation Rule for Context-Free Grammar. 04

    1
    (c) Figure shows NFA-^. Draw an FA accepting the same language. 07

    OR
    Q.3 (a) Define Constant functions, Successor functions and Projection function. 03
    (b) Let G be the grammar 04
    S  aB | bA
    A  a | aS | bAA
    B  b | bS | aBB
    For string aaabbabbba, find Left most derivation and Right most derivation.
    (c) Let M1, M2 and M3 be the FAs pictured in Figure, recognizing languages L1, L2 07
    and L3, respectively.

    0,1
    M3 = R S
    0,1 S

    Draw FAs recognizing the following languages.


    a. L1 U L2
    b. L1 ∩ L3
    Q.4 (a) Decide whether the given language is a CFL, and prove your answer. 03
    L = { xyx | x, y ϵ {a, b}* and |x| ≥ 1}
    (b) Construct PDA for 04
    S  0AB
    A  1A | 1
    B  0B | 1A | 0
    Trace the string 01011 using PDA.
    (c) Give transition tables for deterministic PDA recognizing following language: 07
    L = {x ϵ {a, b}* | na(x) ≠ nb(x)}
    Trace it for the string abbaababbb

    OR
    2
    Q.4 (a) Show using pumping lemma that the given language is not a CFL. 03
    L = { anb2nan | n ≥ 0}
    (b) Prove that There are CFLs L1 and L2 so that L1 ∩ L2 is not a CFL, and there is a 04
    CFL L so that L’ is not a CFL.
    (c) For the PDA, ( {q0, q1}, {0, 1}, {0, 1, z0}, δ, q0, z0, ϕ ), 07
    where δ is
    δ(q0, ɛ, z0) = {(q1, ɛ)}
    δ(q0, 0, z0) = {(q0, 0z0)}
    δ(q0, 0, 0) = {(q0, 00)}
    δ(q0, 1, 0) = {(q0, 10)}
    δ(q0, 1, 1) = {(q0, 11)}
    δ(q0, 0, 1) = {(q1, ɛ)}
    δ(q1, 0, 1) = {(q1, ɛ)}
    δ(q1, 0, 0) = {(q1, ɛ)}
    δ(q1, ɛ, z0) = {(q1, ɛ)}

    Obtain CFG accepted by the above PDA.


    Q.5 (a) Find a regular expression corresponding to each of the following subsets of {0, 03
    1}*
    1. The language of all strings that begin or end with 00 or 11.
    2. The language of all strings containing both 11 and 010 as substrings.
    (b) Define Context-Sensitive Grammar. Write a CSG for {anbncn | n ≥ 1}. 04
    (c) Draw a transition diagram for a Turing machine for the language of all 07
    palindromes over {a, b}.
    OR

    Q.5 (a) Use the pumping lemma to show that following language is not regular. 03
    L = {xy | x, y ϵ {0, 1}* and y is either x or xr }
    (b) Write Short note on Church-Turing Thesis. 04
    (c) Draw a transition diagram for a Turing machine accepting the language {SS 07
    | S ϵ {a, b}*}.

    *************

    You might also like