Theory of Computation previous year question paper 2022 | HNBGU MCA second semester

Theory of Computation

HNBGU MCA Previous Question Paper 2022

    1. Differentiate between DFA and NFA with examples.

    2. Give the recursive definition of regular expression. Find the language described by the regular expression :

      ab* + a for a,b ℇ ⅀ (An alphabet)

    1. Define Moore and Mealy machines with examples.

    2. Convert the following Mealy machine into an equivalent Moore machine:

    1. Write the regular expression, for the language which contains all the strings over an alphabet ⅀ {0,1} ending with 011.

    2. Minimize the following DFA:

      Minimize the following DFA
    1. Define context free grammar with example.

    2. Reduce the following grammar into Chomsky Normal Form:

      G = ({S,A,B,C},{A,B},S,{S->aC, A->aB | bAB, B->b, C->c})

    1. Define Pushdown automaton with example. Is it possible to construct PDA for context free grammar?

    2. Design a PDA for the language.

      L={ww^r | w ℇ {0,1} and w^r is reverse of w.}

    1. How to define transition in Turing Machine? Give Id representation of Turing machine with example.

    2. Design Turing machine that accepts the language

      L = {a^nb^n|n>=1}

  1. Write short note on any two of the following:

    1. Pumping lemma for regular sets.
    2. Chomsky's hierarchy of grammars.
    3. ℇ-NFA
    4. State elimination method for converting Finite Automaton to Regular Expression