cs3021_2026T2_Q1_NA.pdf

Theory of Computation · Quiz 1 · May 2026

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

Let [[IMAGE:7d82534159abbfa4_2_2]] be the language over [[IMAGE:7d82534159abbfa4_2_3]] accepted by a DFA such that every string in [[IMAGE:7d82534159abbfa4_2_4]] contains an odd number of symbols 1. Which of the following languages can be accepted by such a DFA?

[[IMAGE:7d82534159abbfa4_2_5]]
[[IMAGE:7d82534159abbfa4_2_6]]
[[IMAGE:7d82534159abbfa4_2_7]]
[[IMAGE:7d82534159abbfa4_2_8]]

A published solution is not available for this question yet.

Question 3 MCQ · 3.0 marks

Suppose an NFA has [[IMAGE:7d82534159abbfa4_2_9]] states and exactly one accepting state. If all subsets are reachable in subset construction, how many non-accepting states will the equivalent DFA contain?

[[IMAGE:7d82534159abbfa4_3_10]]
[[IMAGE:7d82534159abbfa4_3_11]]
[[IMAGE:7d82534159abbfa4_3_12]]
[[IMAGE:7d82534159abbfa4_3_13]]

A published solution is not available for this question yet.

Question 4 MCQ · 3.0 marks

Which of the following languages is NOT regular?

[[IMAGE:7d82534159abbfa4_3_14]]
[[IMAGE:7d82534159abbfa4_3_15]]
[[IMAGE:7d82534159abbfa4_3_16]]
[[IMAGE:7d82534159abbfa4_3_17]]

A published solution is not available for this question yet.

Question 5 MCQ · 3.0 marks

Consider the following parse tree. [[IMAGE:7d82534159abbfa4_3_18]] Which grammar generates the above parse tree?

[[IMAGE:7d82534159abbfa4_4_19]]
[[IMAGE:7d82534159abbfa4_4_20]]
[[IMAGE:7d82534159abbfa4_4_21]]
[[IMAGE:7d82534159abbfa4_4_22]]

A published solution is not available for this question yet.

Question 6 MCQ · 3.0 marks

Consider the following DFA. [[IMAGE:7d82534159abbfa4_4_23]] Using state elimination, what regular expression describes the language accepted by the DFA?

[[IMAGE:7d82534159abbfa4_4_24]]
[[IMAGE:7d82534159abbfa4_4_25]]
[[IMAGE:7d82534159abbfa4_4_26]]
[[IMAGE:7d82534159abbfa4_4_27]]

A published solution is not available for this question yet.

Question 7 MSQ · 3.0 marks

Which of the following regular expressions generate only strings containing at least two [[IMAGE:7d82534159abbfa4_5_28]] 's?

[[IMAGE:7d82534159abbfa4_5_29]]
[[IMAGE:7d82534159abbfa4_5_30]]
[[IMAGE:7d82534159abbfa4_5_31]]
[[IMAGE:7d82534159abbfa4_5_32]]

A published solution is not available for this question yet.

Question 8 MSQ · 3.0 marks

Which grammars are ambiguous?

[[IMAGE:7d82534159abbfa4_5_33]]
[[IMAGE:7d82534159abbfa4_5_34]]
[[IMAGE:7d82534159abbfa4_5_35]]
[[IMAGE:7d82534159abbfa4_5_36]]

A published solution is not available for this question yet.

Question 9 MSQ · 3.0 marks

Consider: [[IMAGE:7d82534159abbfa4_5_37]] and [[IMAGE:7d82534159abbfa4_6_38]] Which statements are TRUE?

[[IMAGE:7d82534159abbfa4_6_39]]
[[IMAGE:7d82534159abbfa4_6_40]]
[[IMAGE:7d82534159abbfa4_6_41]]
[[IMAGE:7d82534159abbfa4_6_42]]

A published solution is not available for this question yet.

Question 10 MSQ · 3.0 marks

Consider the following DFA over [[IMAGE:7d82534159abbfa4_6_43]] . [[IMAGE:7d82534159abbfa4_6_44]] Which of the following strings are accepted by the DFA?

[[IMAGE:7d82534159abbfa4_6_45]]
[[IMAGE:7d82534159abbfa4_6_46]]
[[IMAGE:7d82534159abbfa4_6_47]]
[[IMAGE:7d82534159abbfa4_6_48]]

A published solution is not available for this question yet.

Question 11 MCQ · 2.0 marks

Let [[IMAGE:7d82534159abbfa4_7_49]] Which language is represented by [[IMAGE:7d82534159abbfa4_7_50]] ?

All strings ending in [[IMAGE:7d82534159abbfa4_7_51]]
All binary strings containing substring [[IMAGE:7d82534159abbfa4_7_52]]
Strings with exactly one occurrence of [[IMAGE:7d82534159abbfa4_7_53]]
Strings beginning with [[IMAGE:7d82534159abbfa4_7_54]]

A published solution is not available for this question yet.

Question 12 MCQ · 2.0 marks

Which grammar is in Chomsky Normal Form (CNF)?

[[IMAGE:7d82534159abbfa4_7_55]]
[[IMAGE:7d82534159abbfa4_7_56]]
[[IMAGE:7d82534159abbfa4_7_57]]
[[IMAGE:7d82534159abbfa4_7_58]]

A published solution is not available for this question yet.

Question 13 MCQ · 2.0 marks

Which statement correctly describes Greibach Normal Form (GNF)?

Every production must begin with a variable.
Every production begins with a terminal followed by zero or more variables.
Productions may contain [[IMAGE:7d82534159abbfa4_8_59]] anywhere.
Only two variables are allowed on RHS.

A published solution is not available for this question yet.

Question 14 NAT · 3.0 marks

A DFA has [[IMAGE:7d82534159abbfa4_8_60]] states. Using the infiniteness-testing theorem, strings of what minimum length must be checked to determine whether the language is infinite?

A published solution is not available for this question yet.

Question 15 NAT · 3.0 marks

Consider the grammar: [[IMAGE:7d82534159abbfa4_8_61]] How many production applications are required to derive [[IMAGE:7d82534159abbfa4_8_62]] using leftmost derivation?

A published solution is not available for this question yet.

Question 16 NAT · 3.0 marks

Let [[IMAGE:7d82534159abbfa4_9_63]] Assume [[IMAGE:7d82534159abbfa4_9_64]] is regular with pumping length [[IMAGE:7d82534159abbfa4_9_65]] . Choose: [[IMAGE:7d82534159abbfa4_9_66]] If [[IMAGE:7d82534159abbfa4_9_67]] , how many [[IMAGE:7d82534159abbfa4_9_68]] 's appear after pumping with [[IMAGE:7d82534159abbfa4_9_69]] ?

A published solution is not available for this question yet.

Question 17 MSQ · 2.0 marks

Which statements about DFA minimization are TRUE?

Equivalent states cannot be distinguished by any continuation string.
States with identical outgoing transitions are always equivalent.
Minimal DFAs for the same language are unique up to isomorphism.
Every DFA state can be merged with at least one other state.

A published solution is not available for this question yet.

Question 18 MSQ · 2.0 marks

Which statements about Context-Free Languages is/are TRUE?

CFLs are closed under union.
CFLs are closed under intersection.
CFLs are closed under intersection with regular languages.
CFLs are closed under complementation.

A published solution is not available for this question yet.

Question 19 MSQ · 2.0 marks

Consider the following NFA. [[IMAGE:7d82534159abbfa4_10_70]] Which strings are accepted by the NFA?

[[IMAGE:7d82534159abbfa4_10_71]]
[[IMAGE:7d82534159abbfa4_10_72]]
[[IMAGE:7d82534159abbfa4_10_73]]
[[IMAGE:7d82534159abbfa4_10_74]]

A published solution is not available for this question yet.

Question 20 NAT · 2.0 marks

Consider the following DFA. [[IMAGE:7d82534159abbfa4_11_75]] What is the minimum length of a string accepted by this DFA that does not contain the symbol **1**?

A published solution is not available for this question yet.