Scribd Logo
Upload

Welcome to Scribd!

  • 0 views

    RSC403-17-18

    Uploaded by

    kumar108

    Copyright:

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

    RSC403-17-18

    Uploaded by

    kumar108
    0 views3 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
    0 views3 pages

    RSC403-17-18

    Uploaded by

    kumar108

    Copyright:

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

    {-r

    1
    Printed Pa Sub Code: RCS403
    Paper Id: Roll No.

    B. TECH
    (SEM I\r) THEORY EXAMINATION 2OI7-I8
    THEORY OF AUTOMATA AND FORMAL LANGUAGES
    Time: 3 Hours Total Marks: 70
    Note: Attempt all sections. If require any missin g data;then choose suitably.

    SECTIOI\ A
    1. Attempt all questions in brief. 2x7=14
    a. Define alphabet, string and language.
    b. Design a regular expression that accepts a[ the strings for input alphabet
    {a,b}
    containing exactly 2 a?s.
    c. Design u wFa that accepts all the strings for input alphabet
    {a,b} containing
    the substring abba.
    d. Define Chomsky hierarchy.
    a
    ls coqtext tree langsage closed u\der union? rf yes, give an example.
    f. NFA into equivalent DFA by takngany suifable example.
    _convert
    o
    b' Remove useless productions from the given productions: s)ar1au,
    A)aAlBla, B)DlE

    SECTION B
    1 Attempt any three of the following:
    2t
    7 x3=21
    a. Define Deterministic Finite Automata (DFA) and design a DFA that accepts
    bf j.
    tbe b)nary zumber wbare equ)ua)eat i,r div.isibte
    b. State recursive definition of regular expression and construct a
    regularexpression corresponding to the state transition diagram as shown in
    Fig.l

    Fig.l
    Reduce the given grammar G:({S,A,B},{qb},P,S) to Chomsky Normal Form.
    Where P is defined as:
    S-+ bA I aB
    -,A+bAAlaSla
    B---+ aBB I bS I b
    d. What is Push Down Automata (PDAX Design the PDA for the language
    1: {wcwR lwe {a,b}*}
    Define Turing Machine (TM). Construct the TM for the language
    1={anbnln>0}.
    SECTION C
    3. Attempt any one part of the following: 7 xl:7

    (a) Describe Mealy and Moore machines with example. Convert the given MealY
    machine as shown in Fig. 2 into Moore Machine.

    ttlZz

    uzl r$24 ;

    1!22
    Fig.2
    (b) Construct the minimum state automata equivalent to DFA described by Fig'

    il. 1

    F'ig. 3
    7 xL-7
    4. Attempt any one part of the following:
    is
    (a) State Pumping Lemma for regular sets. Show that the set L:{aPl P is a Prime}
    not regular.
    complement
    (b) Discuis closure properties i.e. concatenation, union, intersection,
    of regular languages'
    - 7 xL:7
    5. Attempt any one part of the following:
    suitable exarnple'
    (a) Discuss inherent ambiguity of contexl free languages with
    f,""!r*r* that acoepts l*grug" L:{aiuckl 1:i or =
    j
    Construot the oontext
    k; i, j, k are Positive integers).
    (b)Defineparseffee.Findp-arsetreeforthestringabbcdeconsideringthe
    productions-
    S)aAcBe
    A)Ab
    A)b
    B)d
    Is this ambiguous? Justi$z'
    7 xL:1
    6. Attempt any one part of the following:
    and non-deterministic PDA
    (a) Differentiate between deterministic PDA (DPDA)
    (NPDA)*itt,suitaur"example.AlsodiscusstwostackPDAwithexample.
    r--

    (b) Construct a PDA equivalent to the following CFG productions:


    S-+aAA, A+aS IUS lu

    7. Attempt any onepart of the following: 7 xL:7

    (a) Write short notes on the following:


    (D Halting problem of Turing machine
    (iD Recursive Language
    (iiD Variants of Turing Machine
    (b) Define Post's Coffespondence Problem (PCP) and Modified PCP with its
    applications. Find any three PCP solutions of the lists x=(b,bab3,ba) and
    y=(b3,ba,a).

    You might also like