MauryaHub PYQ Practice

cs3021_2026T1_Q2_NA.pdf

Theory of Computation · Quiz 2 · Jan 2026

← Course papers · Start practice / exam

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 MCQ · 3.0 marks

Consider the DFA [[IMAGE:8a942dc8c5e4742c_2_2]] over [[IMAGE:8a942dc8c5e4742c_2_3]] with: • [[IMAGE:8a942dc8c5e4742c_2_4]] • Start state [[IMAGE:8a942dc8c5e4742c_2_5]] • Accepting states [[IMAGE:8a942dc8c5e4742c_2_6]] Transition function [[IMAGE:8a942dc8c5e4742c_2_7]] is defined as: [[IMAGE:8a942dc8c5e4742c_2_8]] Which of the following statements correctly describes the language accepted by [[IMAGE:8a942dc8c5e4742c_2_9]] ?
Source diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notation
  1. All strings that contain at least two consecutive [[IMAGE:8a942dc8c5e4742c_2_10]] s and end in [[IMAGE:8a942dc8c5e4742c_2_11]]
    Source diagram or notationSource diagram or notation
  2. All strings that contain at least two consecutive [[IMAGE:8a942dc8c5e4742c_2_12]] s
    Source diagram or notation
  3. All strings that end in [[IMAGE:8a942dc8c5e4742c_2_13]]
    Source diagram or notation
  4. All strings where after the last occurrence of [[IMAGE:8a942dc8c5e4742c_2_14]] , there are at least two [[IMAGE:8a942dc8c5e4742c_2_15]] s
    Source diagram or notationSource diagram or notation

A published solution is not available for this question yet.

Question 3 MCQ · 3.0 marks

Let [[IMAGE:8a942dc8c5e4742c_3_16]] be defined as: [[IMAGE:8a942dc8c5e4742c_3_17]] What is the minimum number of states in a DFA recognizing [[IMAGE:8a942dc8c5e4742c_3_18]] ?
Source diagram or notationSource diagram or notationSource diagram or notation
  1. 2
  2. 3
  3. 4
  4. 5

A published solution is not available for this question yet.

Question 4 MCQ · 3.0 marks

Consider the grammar: [[IMAGE:8a942dc8c5e4742c_3_19]] For the string [[IMAGE:8a942dc8c5e4742c_3_20]] , what is the minimum possible height of a parse tree? (Height = number of nodes on the longest root-to-leaf path, including the [[IMAGE:8a942dc8c5e4742c_3_21]] leaf)
Source diagram or notationSource diagram or notationSource diagram or notation
  1. 3
  2. 4
  3. 5
  4. 6

A published solution is not available for this question yet.

Question 5 MCQ · 3.0 marks

Consider the language: [[IMAGE:8a942dc8c5e4742c_3_22]] Which of the following statements is **not True**?
Source diagram or notation
  1. [[IMAGE:8a942dc8c5e4742c_3_23]] is not context-free
    Source diagram or notation
  2. Pumping lemma for CFL can be used to prove L is not context-free
  3. [[IMAGE:8a942dc8c5e4742c_4_24]] is context-free
    Source diagram or notation
  4. [[IMAGE:8a942dc8c5e4742c_4_25]] is context-sensitive
    Source diagram or notation

A published solution is not available for this question yet.

Question 6 MCQ · 3.0 marks

Which of the following problems is undecidable?
  1. Whether a DFA accepts a string
  2. Whether a CFG generates a given string
  3. Whether a Turing Machine halts on a given input
  4. Whether a PDA accepts a string

A published solution is not available for this question yet.

Question 7 NAT · 3.0 marks

Consider the NFA [[IMAGE:8a942dc8c5e4742c_4_26]] over [[IMAGE:8a942dc8c5e4742c_4_27]] with: • [[IMAGE:8a942dc8c5e4742c_4_28]] • Start state = [[IMAGE:8a942dc8c5e4742c_4_29]] • Accepting state [[IMAGE:8a942dc8c5e4742c_4_30]] Transition function [[IMAGE:8a942dc8c5e4742c_4_31]] is defined as: [[IMAGE:8a942dc8c5e4742c_4_32]] Construct the equivalent DFA using subset construction, considering only reachable states. How many states will the resulting DFA have?
Source diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notation

    A published solution is not available for this question yet.

    Question 8 NAT · 3.0 marks

    Consider the regular expression over [[IMAGE:8a942dc8c5e4742c_5_33]] : [[IMAGE:8a942dc8c5e4742c_5_34]] How many distinct strings of length exactly 4 are generated by [[IMAGE:8a942dc8c5e4742c_5_35]] ?
    Source diagram or notationSource diagram or notationSource diagram or notation

      A published solution is not available for this question yet.

      Question 9 NAT · 3.0 marks

      Consider a Pushdown Automaton (PDA) [[IMAGE:8a942dc8c5e4742c_5_36]] defined as follows: • [[IMAGE:8a942dc8c5e4742c_5_37]] • [[IMAGE:8a942dc8c5e4742c_5_38]] • [[IMAGE:8a942dc8c5e4742c_5_39]] • Start state: [[IMAGE:8a942dc8c5e4742c_5_40]] • Initial stack symbol: [[IMAGE:8a942dc8c5e4742c_5_41]] • [[IMAGE:8a942dc8c5e4742c_5_42]] (acceptance by empty stack) The transition function [[IMAGE:8a942dc8c5e4742c_5_43]] is defined as: • [[IMAGE:8a942dc8c5e4742c_6_44]] • [[IMAGE:8a942dc8c5e4742c_6_45]] • [[IMAGE:8a942dc8c5e4742c_6_46]] • [[IMAGE:8a942dc8c5e4742c_6_47]] That is: • On reading [[IMAGE:8a942dc8c5e4742c_6_48]] , the PDA pushes [[IMAGE:8a942dc8c5e4742c_6_49]] onto the stack • On reading [[IMAGE:8a942dc8c5e4742c_6_50]] , it pops [[IMAGE:8a942dc8c5e4742c_6_51]] if present; otherwise, the stack remains unchanged The PDA accepts a string if, after consuming the entire input, the stack contains only the initial symbol [[IMAGE:8a942dc8c5e4742c_6_52]] . How many strings of length exactly 4 are accepted by this PDA?
      Source diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notationSource diagram or notation

        A published solution is not available for this question yet.

        Question 10 MSQ · 3.0 marks

        Consider the regular expression over [[IMAGE:8a942dc8c5e4742c_6_53]] : [[IMAGE:8a942dc8c5e4742c_6_54]] Which of the following strings is/are accepted by [[IMAGE:8a942dc8c5e4742c_6_55]] ?
        Source diagram or notationSource diagram or notationSource diagram or notation
        1. [[IMAGE:8a942dc8c5e4742c_6_56]]
          Source diagram or notation
        2. [[IMAGE:8a942dc8c5e4742c_6_57]]
          Source diagram or notation
        3. [[IMAGE:8a942dc8c5e4742c_6_58]]
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_7_59]]
          Source diagram or notation
        5. [[IMAGE:8a942dc8c5e4742c_7_60]]
          Source diagram or notation

        A published solution is not available for this question yet.

        Question 11 MSQ · 3.0 marks

        Let [[IMAGE:8a942dc8c5e4742c_7_61]] be regular languages over alphabet [[IMAGE:8a942dc8c5e4742c_7_62]] . Define the language: [[IMAGE:8a942dc8c5e4742c_7_63]] Which of the following statements is/are TRUE?
        Source diagram or notationSource diagram or notationSource diagram or notation
        1. [[IMAGE:8a942dc8c5e4742c_7_64]] is regular
          Source diagram or notation
        2. [[IMAGE:8a942dc8c5e4742c_7_65]]
          Source diagram or notation
        3. [[IMAGE:8a942dc8c5e4742c_7_66]] can be recognized using a finite automaton
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_7_67]]
          Source diagram or notation

        A published solution is not available for this question yet.

        Question 12 MSQ · 3.0 marks

        Consider the language: [[IMAGE:8a942dc8c5e4742c_7_68]] Which of the following statements is/are TRUE?
        Source diagram or notation
        1. [[IMAGE:8a942dc8c5e4742c_7_69]] is not regular
          Source diagram or notation
        2. Pumping lemma can be used to prove non-regularity
        3. [[IMAGE:8a942dc8c5e4742c_7_70]] has finitely many Nerode equivalence classes
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_7_71]] is regular since the middle block [[IMAGE:8a942dc8c5e4742c_7_72]] is unrestricted
          Source diagram or notationSource diagram or notation

        A published solution is not available for this question yet.

        Question 13 MSQ · 3.0 marks

        Consider the grammar: [[IMAGE:8a942dc8c5e4742c_8_73]] Which of the following statements is/are TRUE?
        Source diagram or notation
        1. The grammar is ambiguous
        2. There exists a string with more than two distinct parse trees
        3. The language generated is finite
        4. Every string has a unique leftmost derivation

        A published solution is not available for this question yet.

        Question 14 MSQ · 3.0 marks

        Consider a PDA transition: [[IMAGE:8a942dc8c5e4742c_8_74]] Which of the following statements is/are TRUE?
        Source diagram or notation
        1. The stack height increases by 2
        2. The symbol [[IMAGE:8a942dc8c5e4742c_8_75]] remains in the stack
          Source diagram or notation
        3. The symbol [[IMAGE:8a942dc8c5e4742c_8_76]] is removed from the stack
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_8_77]] becomes the new top of the stack
          Source diagram or notation

        A published solution is not available for this question yet.

        Question 15 MSQ · 3.0 marks

        Consider the language: [[IMAGE:8a942dc8c5e4742c_8_78]] Which of the following statements is/are TRUE?
        Source diagram or notation
        1. [[IMAGE:8a942dc8c5e4742c_8_79]] is context-free
          Source diagram or notation
        2. [[IMAGE:8a942dc8c5e4742c_9_80]] is regular
          Source diagram or notation
        3. [[IMAGE:8a942dc8c5e4742c_9_81]] can be written as union of two CFLs
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_9_82]] is not context-free
          Source diagram or notation

        A published solution is not available for this question yet.

        Question 16 MSQ · 3.0 marks

        Consider the following productions over [[IMAGE:8a942dc8c5e4742c_9_83]] : Which of the following productions do NOT satisfy the rules of a Context-Sensitive Grammar (CSG)?
        Source diagram or notation
        1. [[IMAGE:8a942dc8c5e4742c_9_84]]
          Source diagram or notation
        2. [[IMAGE:8a942dc8c5e4742c_9_85]]
          Source diagram or notation
        3. [[IMAGE:8a942dc8c5e4742c_9_86]]
          Source diagram or notation
        4. [[IMAGE:8a942dc8c5e4742c_9_87]]
          Source diagram or notation
        5. [[IMAGE:8a942dc8c5e4742c_9_88]]
          Source diagram or notation

        A published solution is not available for this question yet.

        Question 17 MSQ · 3.0 marks

        Which of the following statements about the CYK algorithm is/are correct?
        1. It requires the grammar to be in Chomsky Normal Form (CNF)
        2. It uses dynamic programming
        3. It works in linear time
        4. It fills a triangular table
        5. It can directly handle left-recursive grammars without conversion

        A published solution is not available for this question yet.

        Question 18 MCQ · 2.0 marks

        Which of the following correctly represents the Chomsky hierarchy (from most powerful to least powerful)?
        1. Type-3 [[IMAGE:8a942dc8c5e4742c_10_89]] Type-2 [[IMAGE:8a942dc8c5e4742c_10_90]] Type-1 [[IMAGE:8a942dc8c5e4742c_10_91]] Type-0
          Source diagram or notationSource diagram or notationSource diagram or notation
        2. Type-0 [[IMAGE:8a942dc8c5e4742c_10_92]] Type-1 [[IMAGE:8a942dc8c5e4742c_10_93]] Type-2 [[IMAGE:8a942dc8c5e4742c_10_94]] Type-3
          Source diagram or notationSource diagram or notationSource diagram or notation
        3. Type-2 [[IMAGE:8a942dc8c5e4742c_10_95]] Type-3 [[IMAGE:8a942dc8c5e4742c_10_96]] Type-1 [[IMAGE:8a942dc8c5e4742c_10_97]] Type-0
          Source diagram or notationSource diagram or notationSource diagram or notation
        4. Type-1 [[IMAGE:8a942dc8c5e4742c_10_98]] Type-0 [[IMAGE:8a942dc8c5e4742c_10_99]] Type-2 [[IMAGE:8a942dc8c5e4742c_10_100]] Type-3
          Source diagram or notationSource diagram or notationSource diagram or notation

        A published solution is not available for this question yet.