cs3021_2026T1_Q1_NA.pdf

Theory of Computation · Quiz 1 · Jan 2026

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

Question 2 MSQ · 3.0 marks

Consider the following DFA. [[IMAGE:8b499c042006d6d0_3_2]] Which of the following strings are accepted by the automaton?

[[IMAGE:8b499c042006d6d0_3_3]]
[[IMAGE:8b499c042006d6d0_3_4]]
[[IMAGE:8b499c042006d6d0_3_5]]
[[IMAGE:8b499c042006d6d0_4_6]]
[[IMAGE:8b499c042006d6d0_4_7]]

A published solution is not available for this question yet.

Question 3 MSQ · 3.0 marks

Which statements about [[IMAGE:8b499c042006d6d0_4_8]] -closures are essential in proving NFA–DFA equivalence?

-closure ensures that all NFA states reachable without consuming input are represented.
-closure removes nondeterminism from the automaton.
Without [[IMAGE:8b499c042006d6d0_4_9]] -closure, some accepting NFA computations may be missed by the DFA.
-closure guarantees that the DFA has fewer states than the NFA.

A published solution is not available for this question yet.

Question 4 MSQ · 3.0 marks

Consider grammar: [[IMAGE:8b499c042006d6d0_4_10]] Which of the following statements is/are TRUE?

Grammar is unambiguous
[[IMAGE:8b499c042006d6d0_4_11]] has exactly one parse tree
[[IMAGE:8b499c042006d6d0_4_12]]
[[IMAGE:8b499c042006d6d0_4_13]]

A published solution is not available for this question yet.

Question 5 MSQ · 3.0 marks

Which of the following grammars is/are in Greibach Normal Form (GNF)?

[[IMAGE:8b499c042006d6d0_5_14]]
[[IMAGE:8b499c042006d6d0_5_15]]
[[IMAGE:8b499c042006d6d0_5_16]]
[[IMAGE:8b499c042006d6d0_5_17]]

A published solution is not available for this question yet.

Question 6 NAT · 4.0 marks

Let [[IMAGE:8b499c042006d6d0_5_18]] be a nondeterministic finite automaton (NFA), where: • [[IMAGE:8b499c042006d6d0_5_19]] is a finite set of states with [[IMAGE:8b499c042006d6d0_5_20]] , • [[IMAGE:8b499c042006d6d0_5_21]] is the input alphabet, • [[IMAGE:8b499c042006d6d0_5_22]] is the transition function, • [[IMAGE:8b499c042006d6d0_5_23]] is the start state, • [[IMAGE:8b499c042006d6d0_5_24]] is the set of accepting states with [[IMAGE:8b499c042006d6d0_5_25]] . Assume that all [[IMAGE:8b499c042006d6d0_5_26]] subsets of [[IMAGE:8b499c042006d6d0_5_27]] are reachable during subset construction, so the equivalent DFA [[IMAGE:8b499c042006d6d0_5_28]] has exactly [[IMAGE:8b499c042006d6d0_5_29]] reachable states. A DFA state [[IMAGE:8b499c042006d6d0_6_30]] is accepting if and only if [[IMAGE:8b499c042006d6d0_6_31]] .How many accepting states does the DFA [[IMAGE:8b499c042006d6d0_6_32]] have?

A published solution is not available for this question yet.

Question 7 MSQ · 4.0 marks

Consider the following nondeterministic finite automaton (NFA). The start state is [[IMAGE:8b499c042006d6d0_6_33]] , and [[IMAGE:8b499c042006d6d0_6_34]] is/are the only accepting state. **Transition Table:** [[IMAGE:8b499c042006d6d0_6_35]] Which of the following input strings is/are accepted by the NFA?

[[IMAGE:8b499c042006d6d0_6_36]]
[[IMAGE:8b499c042006d6d0_6_37]]
[[IMAGE:8b499c042006d6d0_6_38]]
[[IMAGE:8b499c042006d6d0_6_39]]

A published solution is not available for this question yet.

Question 8 MSQ · 4.0 marks

Consider the following languages over the alphabet [[IMAGE:8b499c042006d6d0_7_40]] : [[IMAGE:8b499c042006d6d0_7_41]] [[IMAGE:8b499c042006d6d0_7_42]] It is known that [[IMAGE:8b499c042006d6d0_7_43]] is a **regular language** and [[IMAGE:8b499c042006d6d0_7_44]] is a **context-free language (CFL)**. Let [[IMAGE:8b499c042006d6d0_7_45]] . Which of the following statements are correct?

The resulting language [[IMAGE:8b499c042006d6d0_7_46]] is regular.
The resulting language [[IMAGE:8b499c042006d6d0_7_47]] is context-free.
[[IMAGE:8b499c042006d6d0_7_48]]
[[IMAGE:8b499c042006d6d0_7_49]]

A published solution is not available for this question yet.

Question 9 MSQ · 4.0 marks

Which of the following languages are infinite and regular?

[[IMAGE:8b499c042006d6d0_7_50]]
[[IMAGE:8b499c042006d6d0_7_51]]
[[IMAGE:8b499c042006d6d0_7_52]]
[[IMAGE:8b499c042006d6d0_7_53]]

A published solution is not available for this question yet.

Question 10 MCQ · 3.0 marks

Let [[IMAGE:8b499c042006d6d0_8_54]] and [[IMAGE:8b499c042006d6d0_8_55]] . What is [[IMAGE:8b499c042006d6d0_8_56]] ?

[[IMAGE:8b499c042006d6d0_8_57]]
[[IMAGE:8b499c042006d6d0_8_58]]
[[IMAGE:8b499c042006d6d0_8_59]]
Empty set

A published solution is not available for this question yet.

Question 11 MCQ · 3.0 marks

Let the alphabet be [[IMAGE:8b499c042006d6d0_8_60]] . Consider the following regular expression: [[IMAGE:8b499c042006d6d0_8_61]] Which of the following languages is denoted by [[IMAGE:8b499c042006d6d0_8_62]] ?

All strings that either start with [[IMAGE:8b499c042006d6d0_8_63]] or end with [[IMAGE:8b499c042006d6d0_8_64]]
[[IMAGE:8b499c042006d6d0_8_65]]
All strings containing substring [[IMAGE:8b499c042006d6d0_8_66]]
[[IMAGE:8b499c042006d6d0_8_67]]

A published solution is not available for this question yet.

Question 12 MCQ · 3.0 marks

Given the following Parse Tree. [[IMAGE:8b499c042006d6d0_9_68]] Which grammar generates this tree?

[[IMAGE:8b499c042006d6d0_9_69]]
[[IMAGE:8b499c042006d6d0_9_70]]
[[IMAGE:8b499c042006d6d0_9_71]]
[[IMAGE:8b499c042006d6d0_9_72]]

A published solution is not available for this question yet.

Question 13 MCQ · 3.0 marks

Consider [[IMAGE:8b499c042006d6d0_9_73]] To prove that [[IMAGE:8b499c042006d6d0_9_74]] is not regular using the Pumping Lemma, the most suitable choice of string is:

[[IMAGE:8b499c042006d6d0_9_75]]
[[IMAGE:8b499c042006d6d0_10_76]]
[[IMAGE:8b499c042006d6d0_10_77]]
[[IMAGE:8b499c042006d6d0_10_78]]

A published solution is not available for this question yet.

Question 14 MCQ · 4.0 marks

Consider the following automaton: [[IMAGE:8b499c042006d6d0_10_79]] Which regular expression correctly represents the language accepted by the automaton?

[[IMAGE:8b499c042006d6d0_10_80]]
[[IMAGE:8b499c042006d6d0_10_81]]
[[IMAGE:8b499c042006d6d0_10_82]]
[[IMAGE:8b499c042006d6d0_10_83]]

A published solution is not available for this question yet.

Question 15 NAT · 3.0 marks

Given the grammar: [[IMAGE:8b499c042006d6d0_11_84]] After removing null productions (keep [[IMAGE:8b499c042006d6d0_11_85]] if needed), what will be the total number of productions?

A published solution is not available for this question yet.

Question 16 NAT · 3.0 marks

Let [[IMAGE:8b499c042006d6d0_11_86]] be the language over [[IMAGE:8b499c042006d6d0_11_87]] defined by [[IMAGE:8b499c042006d6d0_11_88]] What is the minimum number of states in a DFA that recognizes [[IMAGE:8b499c042006d6d0_11_89]] ?

A published solution is not available for this question yet.