Quizzes¶

Quiz 1¶

Questions 1–5: True / False（对 = True；错 = False）. Questions 6–10: choose exactly one answer.

Notation: \(e\) denotes the empty string, and \(\Sigma^*\) is the set of all finite strings over \(\Sigma\). A PDA configuration \((q, u, \alpha)\) lists the current state, unread input, and stack content, with the stack top on the left. A transition \(((p, a, \beta), (q, \gamma))\) consumes \(a\) and replaces the stack prefix \(\beta\) with \(\gamma\). If \(a = e\), it consumes no input.

PDA acceptance convention: some computation must read all input, reach a final state, and leave an empty stack.

1. Let \(\Sigma\) be the alphabet consisting of the single symbol \(a\). The set of all languages over \(\Sigma\) is countable.

   • T
   • F

2. For every NFA \(M = (K, \Sigma, \Delta, s, F)\), replacing \(F\) by \(K - F\) while keeping all other components unchanged gives an NFA for \(\Sigma^* - L(M)\).

   • T
   • F

3. Every regular language can be generated by a context-free grammar.

   • T
   • F

4. If a string has two distinct derivations from the start symbol of a CFG, then the grammar must be ambiguous.

   • T
   • F

5. A PDA can accept an input string even if another computation branch on that same input gets stuck without accepting.

   • T
   • F

6. An NFA has start state \(s\) and exactly these transitions: \((s, e, p)\), \((p, a, p)\), \((p, a, f)\), \((f, b, f)\). Which set of states is reachable after reading \(a\), including all possible \(e\)-moves?

   • A: \(\{p\}\)
   • B: \(\{f\}\)
   • C: \(\{p, f\}\)
   • D: \(\{s, p, f\}\)

7. Which classification is correct for the language \(L = \{a^n b^{2n} : n \ge 0\}\)?

   • A: Regular.
   • B: Context-free but not regular.
   • C: Not context-free.

8. With stack top on the left, apply the PDA transition \(((p, a, A), (q, BA))\) to \((p, ab, AC)\). What is the resulting configuration?

   • A: \((q, b, BAC)\)
   • B: \((q, ab, BAC)\)
   • C: \((q, b, ABC)\)
   • D: \((q, b, BC)\)

9. In the standard CFG-to-PDA construction of Section 3.4, which transition is added for the production \(S \to aSb\)? Let \(q\) be the simulation state; stack top is on the left.

   • A: \(((q, a, S), (q, Sb))\)
   • B: \(((q, e, S), (q, bSa))\)
   • C: \(((q, e, e), (q, aSb))\)
   • D: \(((q, e, S), (q, aSb))\)

10. In the PDA-to-CFG construction, what does the nonterminal \(\langle p, A, q \rangle\) represent? Here \(A\) is a stack symbol, and \(x\) is a terminal string.

    • A: Strings \(x\) that take \((p, x, A)\) to \((q, e, A)\).
    • B: Strings \(x\) that take \((p, x, A)\) to \((q, e, e)\).
    • C: Strings \(x\) that take \((q, x, A)\) to \((p, e, e)\).
    • D: Strings \(x\) accepted by the entire PDA from its initial configuration.

评论区