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

Welcome to Scribd!

  • 62 views

    QP - TCS

    Uploaded by

    Nikhil Apte
    This document appears to be an internal exam from P.V.G's College of Science in Pune from 2011-2012. It contains a 10 mark section with multiple choice and fill in the blank questions about formal languages and automata. The second 10 mark section asks students to write regular expressions, explain conversions between machines, construct context-free grammars, perform set operations, and construct a deterministic finite automaton.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd

    QP - TCS

    Uploaded by

    Nikhil Apte
    62 views3 pages
    This document appears to be an internal exam from P.V.G's College of Science in Pune from 2011-2012. It contains a 10 mark section with multiple choice and fill in the blank questions about formal languages and automata. The second 10 mark section asks students to write regular expressions, explain conversions between machines, construct context-free grammars, perform set operations, and construct a deterministic finite automaton.

    Original Description:

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOC, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document appears to be an internal exam from P.V.G's College of Science in Pune from 2011-2012. It contains a 10 mark section with multiple choice and fill in the blank questions about formal languages and automata. The second 10 mark section asks students to write regular expressions, explain conversions between machines, construct context-free grammars, perform set operations, and construct a deterministic finite automaton.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    62 views3 pages

    QP - TCS

    Uploaded by

    Nikhil Apte
    This document appears to be an internal exam from P.V.G's College of Science in Pune from 2011-2012. It contains a 10 mark section with multiple choice and fill in the blank questions about formal languages and automata. The second 10 mark section asks students to write regular expressions, explain conversions between machines, construct context-free grammars, perform set operations, and construct a deterministic finite automaton.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOC, PDF, TXT or read online from Scribd
    Download as doc, pdf, or txt
    of 3

    Sup.

    Sign with date

    P.V.Gs College of Science, Pune 411009 Internal Exam (Sem / Term I) 2011-12
    For Staff use only

    Marks out of 20: _____

    Roll No.

    Examiners Sign:

    Class : Subject:

    .Y.B.Sc.

    Examiners Name: ..

    Date:

    Total No. of Pages attached = 1(question paper) + ______ =


    For teachers: The number of legal pages to be attached to Question Paper--

    Instructions: Scratching & Overwriting is not permitted. For Section I, answer must be written in the box for evaluation. For empty boxes, no marks will be granted.

    Section I (10 marks)


    1. If | | = n, then value of n = ___ 2. Select the state machines that can be used to represent only Regular

    languages. Choose all that apply. (a) Deterministic Finite Automata (DFA) (b)Push Down Automata (PDA) (c) Non-deterministic Finite Automata (NFA) (d)Post machine
    3. Mention true or false : For any alphabet , * = (*)* - True / False

    4. Fill in the blanks (a) A set with no elements is called ______ set. (b) A set with a single element is called a __________ set.

    5. State true or false


    (a) DFA can have moves. (b) Moore machines can have final states. 6. Fill in the blanks > A Deterministic Finite Automata (DFA) can have ____

    transition(s) for a state and an input symbol, whereas a Non-deterministic

    Finite Automata (NFA) can have ____ transition(s) for a single state and an input symbol. 7. State true or false
    (a) A DFA can have multiple final(accepting) states (b) An NFA can have multiple final(accepting) states.

    8. State true or false (a) Every finite automata has an equivalent Regular Expression
    (b) For any regular expression R,

    R.(R)* = (R)+

    9. For the languages described below, choose the languages that are Regular languages (Choose all that apply)
    (a) L = {anbn/n>=1} (b) L = { a2nbm / n>=0 and m>=0}

    (c) The set of all palindromes over {x, y}


    (d) L = {anbm / n, m>=0, n is not equal to m}

    10. Fill in the blanks If a Context Free Grammar(CFG) is in Chomsky Normal

    Form (CNF), then the productions of the grammar are of the form _______ and _______.

    Section II (10 marks)


    1. Write regular expression for
    (a) The set of all strings in which 5th character from left end is always b

    over {a,b}
    (b) {a2nbm / n>=0 and m is odd no.}

    (c) The set of all strings over {a,b} where all strings must contain exactly 2 bs or exactly 3 bs
    (d) {a2n / n >=0} 2. Explain how we can convert Mealy machine to Moore machine.

    3. Construct CFG for the following languages:


    (a) L = {anbn where n>=0}

    (b)The set of all palindromes over {x, y} 4. Operations on Sets


    (a) Let set A = {a, b} and set B = {b, c}. Find (A U B)* and (A B)*

    (b)Let set A = {1, 2, 3} and set B = {2, 3, 4} Find Cartesian product A X B.


    5. Construct a DFA for the language accepting strings over the alphabet {a, b}

    such that the DFA accepts strings starting with b and not having aba as substring

    Line Format

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    You might also like