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

Welcome to Scribd!

  • 128 views

    KCS-402 2022-23

    Uploaded by

    reshu.tyagi

    Copyright:

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

    KCS-402 2022-23

    Uploaded by

    reshu.tyagi
    128 views2 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    KCS-402 2022-23

    Uploaded by

    reshu.tyagi

    Copyright:

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

    Printed Pages:02 Sub Code:KCS-402

    Paper Id: 238248 Roll No.

    B.TECH
    (SEM IV) THEORY EXAMINATION 2022-23
    THEORY OF AUTOMATA AND FORMAL LANGUAGES
    Time: 3 Hours Total Marks: 100
    Note: Attempt all Sections. If require any missing data; then choose suitably.

    SECTION A

    1. Attempt all questions in brief. 2 x 10 = 20


    (a) What do you understand by grammar?
    (b) What do you mean by ε-Closure in FA?
    (c) State Arden’s Theorem.
    (d) State Kleen’s Theorem.
    (e) Derive the CFG for (a+b)*.
    (f) Explain Chomsky Hierarchy.
    (g) Explain pumping lemma for context free language.
    (h) Draw the graphical representation for PDA.
    (i) Explain Halting Problem of Turing Machine.
    (j) Explain Linear bounded Automata.
    90

    2
    13
    _2
    SECTION B

    2.
    P2

    24
    2. Attempt any three of the following: 10x3=30
    3E

    5.
    (a) Construct a DFA for ternary number divisible by 4.

    .5
    (b) Determine the FA accepted by the language described by the regular expression:
    P2

    (0+1)*0(0+1)*0(0+1)* over the alphabet {0,1} and also mention the accepted language
    ? 17
    Q

    |1
    (c) Consider the grammar with following production rules:
    S→ABD | AC
    3

    A→aA | bAa |a
    :3

    B→bbA | aB | AB
    27

    C→aCa |aD
    D→aD | bC
    :

    Convert the above grammar into Chomsky Normal Form.


    13

    (d) Design a PDA for the language L= {WWT | W= (a+b)* }


    3

    (e) Write short notes on:


    02

    i) Church’s Thesis
    ii) Recursive and Recursive Enumerable Language
    -2
    08

    SECTION C
    5-

    3. Attempt any one part of the following: 10x1=10


    |0

    (a) Construct a DFA equivalent to the NFA

    QP23EP2_290 | 05-08-2023 13:27:33 | 117.55.242.132


    (b) Construct a minimum state automata equivalent to a DFA whose transition table is
    as follows where q3 and q4 are final state.

    State/ Input
    A b
    Q0 Q1 Q2
    Q1 Q4 Q3
    Q2 Q4 Q3
    Q3 Q5 Q6
    Q4 Q7 Q6
    Q5 Q3 Q6
    Q6 Q6 Q6
    Q7 Q4 Q6

    4. Attempt any one part of the following: 10x1=10


    (a) Find the regular expression corresponding to the finite automata given below:

    (b) State pumping lemma for regular language. Prove that the language L= {ap | p is
    prime} is not regular. 90

    2
    13
    _2
    5. Attempt any one part of the following: 10x1=10

    2.
    P2

    24
    (a) A context free grammar G is given by the following productions:
    E→E+E|E-E|E∗E|E^E|N
    3E

    5.
    N→0|1|2|3|4|5|6|7|8|9

    .5
    P2

    Determine whether the grammar G is ambiguous or not.If ambiguous then construct


    an unambiguous grammar equivalent to G.
    17
    Q

    (b) Explain Closure properties of regular language.


    |1
    3

    6. Attempt any one part of the following: 10x1=10


    :3

    n n n
    (a) Design a two stack PDA for the language L={a b c | n>=1}
    27

    (b) Generate CFG for the given PDA M is defined as


    :

    M = ({q0, q1}, {0,1} {x, z0}, δ, q0, z0, q1) where δ is given as follows: δ (q0,1, z0) =
    13

    (q0, xz0)
    δ (q0,1, x) = (q0, xx)
    3

    δ (q0,0, x) = (q0, x)
    02

    δ (q0, ε, x) = (q1, ε)
    -2

    δ (q1, ε, x) = (q1, ε)
    δ (q1,0, x) = (q1, xx)
    08

    δ (q1,0, z0) = ( q1, ε)


    5-
    |0

    7. Attempt any one part of the following: 10x1=10


    (a) Design a Turing Machine for the language:
    L={an bncn | n>=1}
    (b) Write short notes on:
    (i) Variants of Turing Machine
    (ii) Post Correspondence problem
    (iii) Universal Turing Machine

    QP23EP2_290 | 05-08-2023 13:27:33 | 117.55.242.132

    You might also like