Theory of Computation Questions and Answers

Answer: D

The false statement is Every DFA that accepts \(L\) has \(\gt 2^{n}\) states.

The subset construction turns an n-state NFA into an equivalent DFA whose states are sets of NFA states, so at most \(2^{n}\) states are needed. A DFA with more than \(2^{n}\) states is never forced, which makes the last statement false.

The other three are true. An NFA with n states is not necessarily minimal, so L may have an NFA with fewer states. A DFA can sometimes be smaller than a given NFA (for instance when the NFA has redundant states). And the subset construction itself proves that a DFA with at most \(2^{n}\) states exists. Only the last statement is false, which is why this multiple-select question has the single key it does.

Answer: C

The DFA accepts the set of all strings ending with the pattern \(bab\).

Read the states left to right as remembering how much of bab the input has just seen: the start state (nothing useful), state 2 (last symbol b), state 3 (last two symbols ba) and the accepting state 4 (last three symbols bab). Each transition keeps this meaning: from 4, an a leaves the string ending in ba (state 3) and a b leaves it ending in b (state 2); from 3, an a gives baa, which ends with no useful prefix (start).

So a string is accepted exactly when it ends in bab. 'Containing bab' is wrong because baba contains bab but ends in state 3. 'Not containing aba' fails on ab, which does not contain aba but is rejected. 'Even number of b's' fails on bb, which has two b's but is rejected.

Answer: B

Only II is true.

Statement I is false. An NFA can have every state accepting and still reject strings, because it may have no transition for some symbol: an NFA with one accepting start state and no transitions accepts only \(\varepsilon\). (It would hold for a complete DFA, where every string reaches some state.)

Statement II is true: take \(A = \varnothing\), which is regular. For every language \(B\), \(A \cap B = \varnothing\), which is regular.

So options claiming I is true are wrong, and so is the option calling both false.

Answer: B

The language is \(0^{*} + (1 + 0(00)^{*})(11)^{*}\).

From the start, an \(\epsilon\)-move reaches either state 2 or state 4. Through state 2, pairs of 0s loop 2 to 3 to 2, so \((00)^{*}\) is accepted at 2; after an odd number of 0s, \(0(00)^{*}\), the machine is at 3 and can take the \(\epsilon\)-move to the accepting state 5, then read \((11)^{*}\) looping 5 to 4 to 5. Through state 4, one 1 reaches 5, then \((11)^{*}\). So

\[ L = (00)^{*} + 0(00)^{*}(11)^{*} + 1(11)^{*} \]

Since \((00)^{*} + 0(00)^{*} = 0^{*}\), this is exactly \(0^{*} + (1 + 0(00)^{*})(11)^{*}\).

\((00)^{*} + 1(11)^{*}\) misses strings such as 0 and 011. The third option includes 11, which M rejects. The last omits the empty string, which M accepts at state 2, and strings such as 00011.

Answer: D

The statement that is necessarily true is \(k \le 2^{n}\).

The subset construction turns an NFA with \(n\) states into an equivalent DFA whose states are sets of NFA states, so it has at most \(2^{n}\) states. The minimal DFA has no more states than this DFA, so \(k \le 2^{n}\) always holds.

The other bounds can fail. An NFA may have redundant states, so the minimal DFA can be much smaller than \(n\), which rules out \(k \ge n\) and \(k \ge 2^{n}\). And some languages need the full exponential blow-up, such as 'the \(n\)th symbol from the end is a', which an NFA recognises with \(n + 1\) states but any DFA needs \(2^{n}\), so \(k \le n^{2}\) is not guaranteed.

Answer: C

The language is \(1(0+11)^{*}\).

From the start state s, a 0 goes to the dead state r, which loops on everything, so every accepted string begins with 1, which reaches the final state p. From p, a 0 loops back to p, and a 1 goes to q, from which a second 1 returns to p while a 0 falls into r. So once in p, the machine stays in an accepting state exactly when the rest of the input is a sequence of blocks '0' and '11', which is \((0+11)^{*}\).

\(0(0+1)^{*}\) describes strings starting with 0, all of which are rejected. \(1(0^{*}11)^{*}\) and \(1(110^{*})^{*}\) both fail to generate 10, which the DFA accepts (s to p on 1, p to p on 0): in the first, anything after the leading 1 must end in 11, and in the second, it must begin with 11.

Answer: B

The NFA accepts 0110.

From the start state A, the machine can stay in A on any symbol, or guess that a pair is starting: on 0 it can go to B, which needs another 0 to reach D, and on 1 it can go to C, which needs another 1 to reach D. D is accepting and keeps every later symbol. So the NFA accepts exactly the strings that contain 00 or 11 somewhere.

0110 contains 11: stay in A on 0, go A to C on the first 1, C to D on the second 1, then stay in D on 0. It is accepted.

101010 alternates and never has two equal symbols in a row, so no path reaches D and it is rejected. That rules out 'only A' and 'both A and B'.