Your Answer : (Not Answered)

Correct Answer : D

The equivalent statement is M accepts all input strings in L and rejects all input strings in {0,1}* - L.

A Turing machine decides L when it halts on every input, accepting exactly the strings of L and rejecting all the others. Both halves are needed.

'Halts on all input strings' says nothing about which strings are accepted, so M could decide a different language. 'Accepts all input strings in L' is only recognition: M might accept other strings too, or loop forever on strings outside L. 'Rejects all strings outside L' is the mirror image and says nothing about the strings in L.

Your Answer : (Not Answered)

Correct Answer : B

The recursively enumerable languages are closed under intersection.

Given Turing machines that accept L1 and L2, a new machine can run both on the input, alternating steps, and accept once both have accepted. It accepts exactly the strings in both languages, so L1 ∩ L2 is recursively enumerable.

The others are false. RE languages are not closed under complement: the halting language is RE, but its complement is not, since a language whose complement is also RE would be recursive. The recursive languages are a subset of the RE ones, not the other way round. And there are only countably many Turing machines, so the set of RE languages is countable.

Your Answer : (Not Answered)

Correct Answer : D

The true statements are I, II and III only.

• I: the complement of a recursive language is recursive, hence recursively enumerable, and the union of two recursively enumerable languages is recursively enumerable. True.
• II: every context-free language is recursive (membership is decidable, for example by the CYK algorithm), so its complement is recursive, and recursive languages are closed under union. True.
• III: \(L_{1}^{*}\) is regular, and the intersection of a regular language with a context-free language is context-free. True.
• IV: context-free languages are not closed under complement, so \(\overline{L_{2}}\) need not be context-free, and its union with a regular language need not be either. Not always true.

So the options listing only I, or I with III, leave out true statements, and the option including IV includes a false one.

Your Answer : (Not Answered)

Correct Answer : A

The constraint that always forces v into S is The degree of v is at least k + 1.

If v were not in S, every edge at v would have to be covered by its other endpoint, so all of v's at least k + 1 neighbours would be in S. That makes S larger than k, a contradiction. So v must be in every minimum vertex cover.

The other conditions do not force it. In the path a-b-c the minimum cover is {b}, so k = 1, and a lies on a path of length 2 = k + 1 without being in the cover. In a triangle k = 2, every vertex lies on a cycle of length 3 = k + 1 and in a clique of size 2 = k, yet any one vertex can be left out of a minimum cover.

Your Answer : (Not Answered)

Correct Answer : B

\(L_{1}\) is context-free while \(L_{2}\) is not context-free.

\(L_{1} = \{a^{n}b^{m}c^{n+m}\}\) is context-free: rewrite it as \(a^{n}b^{m}c^{m}c^{n}\), which nests a \(b^{m}c^{m}\) block inside an \(a^{n} \ldots c^{n}\) block. The grammar \(S \rightarrow aSc \mid aTc\), \(T \rightarrow bTc \mid bc\) generates it, and a pushdown automaton pushes for each a and b and pops for each c.

\(L_{2} = \{a^{n}b^{n}c^{2n}\}\) needs the counts of a, b and c compared together, like \(a^{n}b^{n}c^{n}\). A single stack cannot check both equalities, and the pumping lemma for context-free languages shows it is not context-free.

So the options calling \(L_{2}\) context-free, or \(L_{1}\) not context-free, are wrong.

Your Answer : (Not Answered)

Correct Answer : C

The correct statement is \(L_{1}\) is not a context-free language but \(L_{2}\) is a context-free language.

\(L_{2} = \{a^{m}b^{n}c^{m+n}\}\) is context-free: a pushdown automaton pushes a symbol for each a and each b and pops one for each c. A grammar is \(S \rightarrow aSc \mid aBc\), \(B \rightarrow bBc \mid bc\), which wraps each a and each b with its own c.

\(L_{1} = \{a^{m}b^{m}c^{m+n}\}\) needs the a's and b's to be equal and the c's to exceed them. A single stack cannot do both: matching a's against b's uses up the count before the c's arrive. The pumping lemma confirms it with \(a^{p}b^{p}c^{p+1}\): any pumped segment of length at most p either upsets the a = b balance or, by pumping, makes the a's and b's reach or pass the number of c's, or the c's fall to the number of a's.

So only option C is right; options A and B wrongly call \(L_{1}\) context-free, and D wrongly excludes \(L_{2}\).

Your Answer : (Not Answered)

Correct Answer : C

The correct statement is L₁ is not regular, but L₂ is regular.

L₂ is regular. Here \(\alpha\) is a string of a's only, so a word \(\alpha\beta\alpha\) starts and ends with a. Conversely, any word over {a, b} that starts with a, ends with a and has length at least 3 can be written with \(\alpha = a\) and \(\beta\) the nonempty middle. So L₂ is the language of the expression \(a(a + b)^{+}a\), which is regular.

L₁ is not regular. Now \(\alpha\) can be any string over {a, b}, so the first and last symbols of a word need not be equal. Take the words \(a b^{i} a a b^{j}\) with \(i, j \ge 1\). Such a word ends in b, so \(\alpha\) must end in b, and being a prefix \(\alpha\) must start with a. The only suffix starting at an a and ending in b that is short enough is \(a b^{j}\) (the longer suffix \(a a b^{j}\) would need the word to start with aa, but it starts with ab). That \(\alpha\) is also a prefix exactly when \(i \ge j\), and then the middle part is nonempty. So

\[ \begin{aligned} L_{1} \cap a b^{+} a a b^{+} &= \\ & \{ a b^{i} a a b^{j} \mid i \ge j \ge 1 \} \end{aligned} \]

This language is not regular, since a finite automaton cannot compare the number of b's before and after the aa. Regular languages are closed under intersection with the regular language \(a b^{+} a a b^{+}\), so if L₁ were regular this intersection would be regular. Hence L₁ is not regular.

The easy mistake is to read L₁ as the words whose first and last symbols are equal, which is regular. That ignores that \(\alpha\) may have several symbols and that only the word as a whole has to start and end with the same string \(\alpha\). So option C is correct, and A, B and D are not.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct 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.

Your Answer : (Not Answered)

Correct Answer : A

The language is \(\{a^{m}b^{n} \mid 1 \le m \text{ and } n \lt m\}\).

In state s each a pushes an A, so after \(a^{m}\) the stack holds m A's above \(\bot\). Each b in state p pops one A. To empty the stack the PDA must reach q, where it can pop all remaining A's and finally \(\bot\). But both moves into q, from s or from p, need an A on top of the stack.

• With no a's (m = 0) the top is \(\bot\) and q is unreachable, so \(m \ge 1\).
• After n b's, \(m - n\) A's remain; moving to q needs at least one, so \(n \lt m\). With n = m the stack shows \(\bot\) in p and the PDA is stuck.

\(0 \le n \le m\) wrongly allows n = m and m = 0, the empty string included. \(0 \le m, 0 \le n\) has no relation between the counts at all. Strings of b's alone cannot be accepted, since b needs an A to pop, which rules out the last option.

Your Answer : (Not Answered)

Correct Answer : A

A deterministic pushdown automaton can accept any regular language.

Every regular language has a deterministic finite automaton, and a DPDA can simulate a DFA by simply never using its stack. So every regular language is a deterministic context-free language.

The reverse does not hold for the other classes. Some context-free languages, such as even-length palindromes, need nondeterminism (the machine must guess the middle), so not every context-free language, or every language of a nondeterministic PDA, is accepted by a DPDA. Decidable languages include non-context-free ones such as aⁿbⁿcⁿ, which no pushdown automaton accepts.

Your Answer : (Not Answered)

Correct Answer : D

The true statement is \(L = \{a^{n} \mid n \ge 0\} \cup \{a^{n}b^{n} \mid n \ge 0\}\) and is deterministic context-free.

The start state is accepting and pushes one X for each a, so any string of a's alone, including the empty string, ends in an accepting state: that gives \(a^{n}\). On the first b the PDA pops an X and moves to the middle state, which pops one X per further b. When the stack is back to Z it takes the \(\varepsilon\) move to the final accepting state. So a's followed by an equal number of b's are accepted: \(a^{n}b^{n}\).

At every point there is at most one move for each combination of state, input and stack top, and the \(\varepsilon\) move on Z does not compete with any input move on Z. The PDA is deterministic, so \(L\) is deterministic context-free, which rules out the option saying no DPDA accepts it. \(L\) is not just \(\{a^{n}b^{n}\}\), since strings like aa are accepted, and every context-free language is decided by some halting Turing machine.

Your Answer : (Not Answered)

Correct Answer : D

The automaton's language is \((ba^{*}a + ab^{*}b)^{*}(ab^{*} + ba^{*})\).

Every run starts at the start state. A round trip through the upper state reads \(a\), any number of \(b\)s on its loop, then the \(b\) back: \(ab^{*}b\). A round trip through the lower state reads \(ba^{*}a\). A run may take any number of these round trips in any order, then must finish in an accepting state, either by \(a\) followed by \(b\)s (\(ab^{*}\)) or by \(b\) followed by \(a\)s (\(ba^{*}\)).

Option A allows exactly one round trip, so it misses even the single letter a. Option B never mixes the two kinds of round trip, so it misses abbaa, which the automaton accepts as the round trip ab followed by the finish baa. Option C accepts the empty string and strings such as aa, but the start state is not accepting and has no way to read aa.

Your Answer : (Not Answered)

Correct Answer : A

The equivalent expression is \(0^{*}1(0 + 10^{*}1)^{*}\).

Only 1s change the state, and each 1 moves between the two states, so the DFA accepts exactly the strings with an odd number of 1s. \(0^{*}1\) reads any 0s and the first 1, reaching the accepting state. From there, \((0 + 10^{*}1)^{*}\) repeatedly either reads a 0 (staying put) or reads a 1, any 0s, and a 1 (leaving and coming back), so it always returns to the accepting state and can generate every such continuation.

\(0^{*}(10^{*}11)^{*}0^{*}\) accepts the empty string, which has no 1s. \(0^{*}1(010^{*}1)^{*}0^{*}\) cannot generate 11 followed by 1 (that is, 111), and \(0(1 + 0^{*}10^{*}1)^{*}0^{*}\) insists on a leading 0 and accepts 0 alone.

Your Answer : (Not Answered)

Correct Answer : D

The correct statement is Only I, II and III are undecidable.

• I: unrestricted grammars generate exactly the recursively enumerable languages, so their membership problem is as hard as the halting problem: undecidable.
• II: being regular is a non-trivial property of the language of a Turing machine, so by Rice's theorem it is undecidable.
• III: equivalence of two grammars is undecidable already for context-free grammars, so it is undecidable for grammars in general.
• IV: an NFA accepts a regular language, and every regular language is accepted by a deterministic PDA (a DFA that ignores its stack). The answer is always yes, so the problem is trivially decidable.

The options leaving out I, II or III, or listing IV as undecidable, are therefore wrong.

Your Answer : (Not Answered)

Correct Answer : C

\(L_{1}, L_{2}\) are recursive and \(L_{3}\) is not recursive.

Within its first 2016 steps a Turing machine can read at most the first 2016 or so input symbols. So whether \(M\) takes at least 2016 steps on an input depends only on that input’s first 2016 symbols, and there are finitely many such prefixes. A decider can simulate \(M\) for 2016 steps on each of them and answer whether some (for \(L_{1}\)) or all (for \(L_{2}\)) inputs reach step 2016. Both are therefore recursive.

\(L_{3}\), whether \(M\) accepts the empty string, is a non-trivial property of the language \(M\) accepts, so it is undecidable by Rice’s theorem (it is recursively enumerable, but not recursive).

The options calling \(L_{1}\) or \(L_{2}\) non-recursive overlook the bounded step count, and the option calling all three recursive ignores Rice’s theorem.

Your Answer : (Not Answered)

Correct Answer : A

The language is \(\{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

B generates \(b^{n}\) for \(n \ge 1\) and A generates \(a^{n}\) for \(n \ge 1\). The first rule \(S \rightarrow aaB\) therefore gives exactly two a's followed by one or more b's, \(a^{2}b^{n}\). The second rule \(S \rightarrow Abb\) gives one or more a's followed by exactly two b's, \(a^{n}b^{2}\). The language is the union of the two.

The other options demand a link between the numbers of a's and b's (such as \(a^{n}b^{n}\) or \(a^{n}b^{2n}\)), but in this grammar the a's and b's are generated by separate rules with nothing tying the counts together. For example aabbb is in L(G) but has unequal counts.

Your Answer : (Not Answered)

Correct Answer : D

\(G_{1}\) and \(G_{2}\) generate \(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\).

\(G_{1}\): \(S \rightarrow aS \mid B\) produces any number of a's, possibly none, then switches to \(B\). \(B \rightarrow b \mid bB\) produces one or more b's. So \(m \ge 0\) and \(n \gt 0\).

\(G_{2}\): \(S\) must start with a (then \(A\)) or b (then \(B\)). From \(A\), any number of further a's, then optionally \(B\), which gives any number of b's including none. From the b start, only b's follow. So every string is \(a^{m}b^{n}\) with at least one symbol: \(m \gt 0\) or \(n \gt 0\). The empty string is excluded because \(S\) has no \(\varepsilon\) rule.

The other options get one of these conditions wrong, for example 'm \(\gt\) 0 and n \(\gt\) 0' for \(G_{2}\) would exclude 'a' and 'b', which \(G_{2}\) generates.