Properties of regular languages

Closure: regular languages are closed under every finite operation in the syllabus (∪ ∩ − complement, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient, prefix), not under infinite union or taking subsets. Algorithms exist for membership, emptiness, finiteness, universality, equivalence, containment. The pumping lemma (|xy| ≤ p, |y| ≥ 1, pump all i) proves non-regularity; it is necessary, not sufficient. Fast intuition: bounded facts are regular; exact unbounded comparisons are not; finite and eventually periodic unary sets are regular; a free middle x absorbs the hard part.

1. MSQ

   If L is regular, which are regular?

   1. Lᴿ ∩ L
   2. Prefix(L)
   3. L / { aⁿbⁿ }
   4. { w : w ∈ L and |w| is prime }
2. MCQ

   { aⁱbʲ : i ≥ j } is:

   1. regular
   2. not regular
   3. finite
   4. a*b*
3. NAT

   Minimum states of a DFA for strings over {a,b} where every prefix satisfies |#a − #b| ≤ 1?

   Write your answer before opening the key.

4. MCQ

   To prove L non-regular by the pumping lemma, you choose:

   1. p and the split
   2. w and i
   3. p and i
   4. the split and w
5. MSQ

   Which questions about regular languages have always-terminating algorithms?

   1. emptiness
   2. finiteness
   3. equivalence of two DFAs
   4. universality
6. MCQ

   { ww : w ∈ {a}* } is:

   1. regular — it equals (aa)*
   2. not regular
   3. finite
   4. equal to a*
7. MCQ

   L₁ = {aⁿbⁿ}, L₂ = complement of L₁. L₁ ∪ L₂ is:

   1. not regular
   2. regular (Σ*)
   3. undefined
   4. empty
8. MSQ

   Which are not regular?

   1. { a^{n!} }
   2. { aⁿbᵐcⁿ⁺ᵐ }
   3. { w : w = wᴿ } over {a,b}
   4. { w : |w| ≡ 0 mod 7 }
9. MCQ

   h(a) = ab, h(b) = ε. h⁻¹({ab}) contains:

   1. only a
   2. a with any number of b’s around it
   3. only ab
   4. nothing
10. NAT

    Pumping length guaranteed by a 9-state DFA?

    Write your answer before opening the key.