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

Welcome to Scribd!

  • 13 views

    BEET 405 Theory of Automata & Formal Languages

    Uploaded by

    jatinshaarmaa
    This document contains a 4th semester examination paper for a Bachelor of Technology degree in Computer Science or Information Technology. The exam covers the theory of automata and formal languages. It consists of 5 questions worth 100 total marks. Question 1 has 4 parts worth 5 marks each on topics like designing DFAs and NFAs, pumping lemma theorem, epsilon-closure of states. Question 2 also has 4 parts worth 5 marks each on topics like inherently ambiguous languages, converting grammars to CNF, derivation trees, properties of CFLs, and pushdown automata. Questions 3 and 4 each have 2 parts worth 10 marks each on topics like Myhill-Nerode theorem, NFAs and DFAs, Arden's theorem

    Copyright:

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

    BEET 405 Theory of Automata & Formal Languages

    Uploaded by

    jatinshaarmaa
    13 views2 pages
    This document contains a 4th semester examination paper for a Bachelor of Technology degree in Computer Science or Information Technology. The exam covers the theory of automata and formal languages. It consists of 5 questions worth 100 total marks. Question 1 has 4 parts worth 5 marks each on topics like designing DFAs and NFAs, pumping lemma theorem, epsilon-closure of states. Question 2 also has 4 parts worth 5 marks each on topics like inherently ambiguous languages, converting grammars to CNF, derivation trees, properties of CFLs, and pushdown automata. Questions 3 and 4 each have 2 parts worth 10 marks each on topics like Myhill-Nerode theorem, NFAs and DFAs, Arden's theorem

    Original Description:

    sss

    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 a 4th semester examination paper for a Bachelor of Technology degree in Computer Science or Information Technology. The exam covers the theory of automata and formal languages. It consists of 5 questions worth 100 total marks. Question 1 has 4 parts worth 5 marks each on topics like designing DFAs and NFAs, pumping lemma theorem, epsilon-closure of states. Question 2 also has 4 parts worth 5 marks each on topics like inherently ambiguous languages, converting grammars to CNF, derivation trees, properties of CFLs, and pushdown automata. Questions 3 and 4 each have 2 parts worth 10 marks each on topics like Myhill-Nerode theorem, NFAs and DFAs, Arden's theorem

    Copyright:

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

    BEET 405 Theory of Automata & Formal Languages

    Uploaded by

    jatinshaarmaa
    This document contains a 4th semester examination paper for a Bachelor of Technology degree in Computer Science or Information Technology. The exam covers the theory of automata and formal languages. It consists of 5 questions worth 100 total marks. Question 1 has 4 parts worth 5 marks each on topics like designing DFAs and NFAs, pumping lemma theorem, epsilon-closure of states. Question 2 also has 4 parts worth 5 marks each on topics like inherently ambiguous languages, converting grammars to CNF, derivation trees, properties of CFLs, and pushdown automata. Questions 3 and 4 each have 2 parts worth 10 marks each on topics like Myhill-Nerode theorem, NFAs and DFAs, Arden's theorem

    Copyright:

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

    Sub Code: BEET405/BITT405 ROLL NO……………..……………..

    IV SEMESTER EXAMINATION, 2022 – 23


    IInd Yr , B.Tech – Computer Science & Eng/Information Technology
    Theory of Automata and Formal Languages

    Duration: 3:00 hrs Max Marks: 100


    Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing data,
    the same may be assumed and state the assumption made in the answer.

    Q 1. Answer any four parts of the following. 5x4=20


    n m
    a) Design the DFA that accepts L = {a b | n,m >= 1}
    b) Differentiate between DFA and NFA.
    c) State the pumping lemma theorem for regular languages. Show that L = {ap | p is
    a prime} is not regular.
    d) Define ϵ-Closure. Compute ϵ-Closure of states of the given ϵ-NFA.

    e) Construct CFG for Language L = {a2nbn | n > 3}


    f) Explain Post Correspondence Problem with example.
    Q 2. Answer any four parts of the following. 5x4=20
    a) What is inherently ambiguous language? Give example of inherently ambiguous
    language.
    b) Convert the following grammar G to CNF
    S →aAD, A → aB | bAB , B →b , D → d
    c) Consider the following Grammar S → aAS | a, A → SbA | SS |ba
    Give derivation tree for aabbaa.
    d) Explain the following Decision Properties of CFL’s (i) Emptiness, (ii) Finiteness
    and (iii) Membership
    e) Define Push Down Automata. Explain the basic structure of PDA with a neat
    graphical representation.
    f) Describe Recursive and Recursive Enumerable Languages. Give examples of
    each.
    Q 3. Answer any two parts of the following. 10x2= 20
    a) Explain Myhill-Nerode Theorem using suitable example.
    b) Construct NFA that accepts a set of all strings over {a,b} ending in aba. Use this
    NFA to construct equivalent DFA,
    c) State Arden Theorem. Construct RE corresponding to the given DFA below:
    Q 4. Answer any two parts of the following. 10x2= 20
    a) Define Two-stack PDA? Design Two-stack PDA to accept the language
    L = {anbncn | n ≥ 0}.
    b) Convert the given Context Free grammar into equivalent PDA
    S → 0BB, B → 0S |1S | 0, V= {S, B}, T = {0,1}
    c) What is Turing machine halting problem?
    Q 5. Answer any two parts of the following. 10x2= 20
    a) Explain about Universal Turing Machine?
    b) Design Turing machine and its transition diagram to accept the language
    L = {anbn | n >=1}
    c) Convert the following Mealy machine to equivalent Moore machine

    **********

    You might also like