Scribd Logo
Upload

Welcome to Scribd!

  • 338 views

    Theory of Automata Formal Languages RCS403 PDF

    Uploaded by

    compiler&automata
    This document contains the questions from a theory examination on automata and formal languages. It covers topics such as regular expressions, finite automata, context-free grammars, pushdown automata, Turing machines, and the relationships between them. The exam has 7 sections with multiple choice and descriptive questions testing students' understanding of fundamental concepts in automata theory and formal languages.

    Copyright:

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

    Theory of Automata Formal Languages RCS403 PDF

    Uploaded by

    compiler&automata
    338 views3 pages
    This document contains the questions from a theory examination on automata and formal languages. It covers topics such as regular expressions, finite automata, context-free grammars, pushdown automata, Turing machines, and the relationships between them. The exam has 7 sections with multiple choice and descriptive questions testing students' understanding of fundamental concepts in automata theory and formal languages.

    Original Title

    THEORY-OF-AUTOMATA-FORMAL-LANGUAGES-RCS403.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains the questions from a theory examination on automata and formal languages. It covers topics such as regular expressions, finite automata, context-free grammars, pushdown automata, Turing machines, and the relationships between them. The exam has 7 sections with multiple choice and descriptive questions testing students' understanding of fundamental concepts in automata theory and formal languages.

    Copyright:

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

    Theory of Automata Formal Languages RCS403 PDF

    Uploaded by

    compiler&automata
    This document contains the questions from a theory examination on automata and formal languages. It covers topics such as regular expressions, finite automata, context-free grammars, pushdown automata, Turing machines, and the relationships between them. The exam has 7 sections with multiple choice and descriptive questions testing students' understanding of fundamental concepts in automata theory and formal languages.

    Copyright:

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

    Printed Pages: 03 Sub Code: RCS403

    Paper Id: 110433 Roll No.

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

    SECTION A

    1. Attempt all questions in brief. 2 x 7 = 14


    a. Define alphabet, string and language.
    b. Design a regular expression that accepts all the strings for input alphabet {a,b}
    containing exactly 2 a’s.
    c. Design a NFA that accepts all the strings for input alphabet {a,b} containing
    the substring abba.
    d. Define Chomsky hierarchy.
    e. Is context free language closed under union? If yes, give an example.
    f. Convert NFA into equivalent DFA by taking any suitable example.
    g. Remove useless productions from the given productions: SAB|ab,
    AaA|B|a, BD|E

    SECTION B

    2. Attempt any three of the following: 7 x 3 = 21


    a. Define Deterministic Finite Automata (DFA) and design a DFA that accepts
    the binary number whose equivalent is divisible by 5.
    b. State recursive definition of regular expression and construct a
    regularexpression corresponding to the state transition diagram as shown in
    Fig.1

    Fig.1
    c. Reduce the given grammar G=({S,A,B},{a,b},P,S) to Chomsky Normal Form.
    Where P is defined as:
    S→ bA | aB
    A→ bAA | aS | a
    B → aBB | bS | b
    d. What is Push Down Automata (PDA)? Design the PDA for the language
    L = {wcwR│w{a,b}*}
    e. Define Turing Machine (TM). Construct the TM for the language
    L = {anbn│n>0}.
    SECTION C
    3. Attempt any one part of the following: 7x1=7
    (a) Describe Mealy and Moore machines with example. Convert the given Mealy
    machine as shown in Fig. 2 into Moore Machine.

    Fig. 2
    (b) Construct the minimum state automata equivalent to DFA described by Fig. 3

    Fig. 3
    4. Attempt any one part of the following: 7x1=7
    p
    (a) State Pumping Lemma for regular sets. Show that the set L={a | p is a prime} is
    not regular.
    (b) Discuss closure properties i.e. concatenation, union, intersection, complement
    of regular languages.
    5. Attempt any one part of the following: 7x1=7
    (a) Discuss inherent ambiguity of context free languages with suitable example.
    Construct the context free grammar that accepts language L={aibjck| i = j or j =
    k; i, j, k are positive integers}.
    (b) Define parse tree. Find parse tree for the string abbcde considering the
    productions-
    SaAcBe
    AAb
    Ab
    Bd
    Is this ambiguous? Justify.
    6. Attempt any one part of the following: 7x1=7
    (a) Differentiate between deterministic PDA (DPDA) and non-deterministic PDA
    (NPDA) with suitable example. Also discuss two stack PDA with example.
    (b) Construct a PDA equivalent to the following CFG productions:
    S→aAA, A→aS│bS│a

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


    (a) Write short notes on the following:
    (i) Halting problem of Turing machine
    (ii) Recursive Language
    (iii) Variants of Turing Machine
    (b) Define Post’s Correspondence 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