Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Important Questions CSE322

    Uploaded by

    ananyaarora141103
    Abcde ef dhdjcjj. J ndjckd

    Copyright:

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

    Important Questions CSE322

    Uploaded by

    ananyaarora141103
    6 views3 pages
    Abcde ef dhdjcjj. J ndjckd

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Abcde ef dhdjcjj. J ndjckd

    Copyright:

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

    Important Questions CSE322

    Uploaded by

    ananyaarora141103
    Abcde ef dhdjcjj. J ndjckd

    Copyright:

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

    Important Questions CSE322

    Unit I: Finite Automata


    1. Define a Finite Automaton.
    A finite automaton is a mathematical model of computation used to simulate sequential
    logic. It consists of a finite set of states, an input alphabet, a transition function, an initial
    state, and a set of accepting states.
    2. Differentiate between DFA and NDFA.
    DFA: Deterministic Finite Automaton has exactly one transition for each input
    symbol from a given state.
    NDFA: Non-Deterministic Finite Automaton can have multiple transitions for the
    same input symbol from a state, including ε-transitions.
    3. Explain the equivalence of DFA and NDFA.
    Every NDFA can be converted into an equivalent DFA by constructing a DFA that
    simulates all possible states of the NDFA simultaneously.
    4. What is a Transition Function?
    The transition function δ(q,a)\delta(q, a) specifies the next state for each state qq and
    input symbol aa.
    5. Describe the process of minimization of Finite Automata.
    The minimization process involves removing unreachable states and merging
    equivalent states to create the smallest DFA that accepts the same language.

    Unit II: Regular Expressions and Regular Sets


    1. Define a Regular Expression.
    A regular expression is a symbolic notation used to describe a regular language. For
    example, a∗ba^*b represents strings with zero or more a′sa's followed by one bb.
    2. State and prove Arden’s Theorem.
    Arden's theorem helps in finding solutions to linear equations in regular expressions. It
    states: If R=Q+RPR = Q + RP, then R=QP∗R = QP^*, provided ε∉Pε \notin P.
    3. Explain the Pumping Lemma for Regular Sets.
    The Pumping Lemma is a property of all regular languages that states if a string ss in a
    regular language LL is long enough, it can be divided into parts xyzxyz such that
    xynzxy^nz is also in LL for any n≥0n \geq 0.
    4. Convert the regular expression (a+b)∗ a(a+b)^*a into a DFA.
    Steps:
    Build an NFA using the Thompson construction.
    Convert the NFA to an equivalent DFA using subset construction.

    Unit III: Formal Languages


    1. What are Chomsky's classifications of languages?
    Type 0: Recursively Enumerable
    Type 1: Context-Sensitive
    Type 2: Context-Free
    Type 3: Regular
    2. Define a grammar.
    A grammar GG is defined as a 4-tuple (N,T,P,S)(N, T, P, S), where:
    NN: Non-terminal symbols
    TT: Terminal symbols
    PP: Production rules
    SS: Start symbol
    3. Explain the concept of Recursive and Recursively Enumerable Sets.
    Recursive Sets: A language is recursive if a Turing machine can decide its
    membership in finite time.
    Recursively Enumerable Sets: A language is recursively enumerable if a Turing
    machine can enumerate all strings in the language.

    Unit IV: Context-Free Languages


    1. What is ambiguity in CFG?
    A CFG is ambiguous if there exists a string that can be derived using two or more
    different parse trees.
    2. Explain the Chomsky Normal Form.
    A context-free grammar is in Chomsky Normal Form if every production is of the form
    A→BCA \to BC or A→aA \to a, where A,B,CA, B, C are non-terminals, and aa is a
    terminal.
    3. What is the Pumping Lemma for Context-Free Languages?
    It states that if LL is a CFL, then any sufficiently long string s∈Ls \in L can be written as
    uvwxyuvwxy such that vv and xx can be "pumped" (repeated any number of times)
    while keeping the resulting string in LL.
    Unit V: Pushdown Automata and Parsing
    1. Define Pushdown Automata (PDA).
    A PDA is a finite automaton with an additional stack storage. It is used to recognize
    context-free languages.
    2. Differentiate between DPDA and NDPDA.
    DPDA: Deterministic PDA has a single computation path for every input.
    NDPDA: Non-Deterministic PDA can have multiple computation paths for the
    same input.
    3. Describe Bottom-Up Parsing.
    Bottom-up parsing constructs a parse tree for an input string starting from the leaves
    (input symbols) and working up to the root (start symbol).

    Unit VI: Turing Machines and Complexity


    1. What is a Turing Machine?
    A Turing machine is a theoretical computing model that manipulates symbols on a tape
    according to a set of rules. It has infinite memory and is capable of simulating any
    algorithm.
    2. Explain the Halting Problem.
    The halting problem asks whether a Turing machine will halt on a given input or run
    forever. It is undecidable, as proven by Alan Turing.
    3. What are Decidable and Undecidable Languages?
    Decidable Languages: A Turing machine can decide membership for every string
    in finite time.
    Undecidable Languages: No Turing machine can decide membership for every
    string.
    4. What is Computational Complexity?
    Computational complexity measures the resources (time and space) required by an
    algorithm to solve a problem as a function of input size.

    You might also like