Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Theory of Computation End Term

    Uploaded by

    Harmanpreet Kaur

    Copyright:

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

    Theory of Computation End Term

    Uploaded by

    Harmanpreet Kaur
    2 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
    2 views2 pages

    Theory of Computation End Term

    Uploaded by

    Harmanpreet Kaur

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    End-Term Examination

    (CBCS)(SUBJECTIVE lYPE){Offline)
    Course Name:<B.Tech IT/ CSE-Al/ CSE>, Semester.<5>
    (November-Decem ber, 2023)

    / Subject Code: BCS 303 • 1 Subject: Theory of Computation \


    Time :3 Hours Maximum Marks :GO
    ! Note:Q. 1 is compul'sory. Attempt one question each from the Units I, II, 111 & IV. , \

    Ql (2.5*8=20)
    .A~) How many tuples are used to define a Finite Automata, explain with an
    example?
    L,tb) Design a DFA which accepts all the strings starting with 00 and ending with
    101?
    --{c) What is Greibach Normal Form, explain with an example?
    \ (d) Discuss about different closure properties of Context Free Grammar (CFG)?
    Jef What is the difference. between Leftmost Derivation tree and Rightmost
    Derivation tree, draw the derivation tree for the string id+id*id using
    following productions of the grammar.
    /
    (f) What is a Turing Machine Transducer? Design TM for l's complement.
    . (g') What is the difference between Context Free Language and Context
    Sensitive language, explain with example?
    ~(n) What is halting problem, discuss about it briefly?

    UNIT-I
    (a) Find out whether the strings 00, 01001, 10010, 000, 0000 are (10)
    Q.2.
    \ accepted by the following Nondeterministic Finite Automata
    ' \NFA).
    -
    0 1
    .
    {qo, q1} q1
    *q1 qo {q1, q2}
    '
    q2 ¢ q1

    (b) Convert the above NFA to DFA, explain in detail.

    Explain the steps followed in minimization of Finite Automata and (10)


    ' Q3
    minimize the following finite automata.

    a b
    q1 qo
    q1 qo q2
    q2 q3 q1
    *q3 q3 qo
    q4 q3 qs
    qs q6 q4
    q6 Qs q6
    q7 QG q3

    UNIT-II
    __aa How many tuples are used to define a Pushdown Automata (10)
    (PDA) (describe each tuple) and design a PDA for L = {a0 b2n:
    n>O l on l: = { a, b} .
    Page 1 of 2
    QS (a). Find out whether the grammar is ambiguous of not. (10)
    (Where Eis epsilon - empty string).

    (b). Define Chomsky Normal Form (CNF). Convert the following


    Context free grammar to CNF.

    UNIT-Ill
    ~6 By writing the Pumping Lemma for context ·free languages find out (10)
    whether the language L = {a"b2"c"/n>l} is context free or not.
    Q7 (a). Design a Turing Machine which accepts the language L = (10)
    {a"b"/n>l} over I= {a,b}.
    (b). Discuss about Chomsky Hierarchy of Languages.
    UNIT-IV
    QS (a). Briefly describe about Complexity classes P and NP. (10)
    (b). convert the following Moore Machine to Mealy Machine.
    Present Next state Output
    State
    a=0 a=l
    q3 qi 0
    Qi Qi q2 1
    q2 q2 q3 0
    l
    - Q3 Q3 qo 0
    Define Mealy Machine with tuples and convert the following Mealy (10)
    ; tg

    -, -
    Machine to Moore Machine.
    J Pres.ent_ I - -
    state
    r

    State
    Input a=O
    . Ne~state

    output
    ·- _.__
    'Input a=l
    ----- - \ - -- -

    State output
    q3 0 Q2 1
    J
    Q2 q1 J 0 q4 0
    q3 q2 1 qi 1
    q4 q4 1 q3 0

    ,.-,~
    ·r D
    Page 2 of 2
    sf
    @

    You might also like