Consider L1 = {a^(z²) | z is an integer}, L2 = {a^(2z) | z ≥ 0}, L3 = {ωω | ω ∈ {a, b}*}. Which of the languages is (are) regular?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. L2 only
Explanation
Even-length strings of a's, (aa)*, are regular. Perfect-square lengths and copies ww are not regular (pumping lemma).
Note: The exponents are garbled in the source; this reading (L2 = a^(2z)) is the one consistent with the official key.
More Theory of Computation and Compilers questions
- Which of the following grammars is (are) ambiguous? (A) S → SS | aSb | bSa | λ (B) S → aSbS | bSaS | λ (C) S → aAB, A → bBb, B → A | λ, whe…
- Match List I with List II (L_R regular, L_CF context-free, L_REC recursive, L_RE recursively enumerable). List I: A. Recursively enumerable…
- Consider the regular expressions r = a(b + a)*, s = a(a + b)⁺, t = aa*b. Which relation holds between the languages they generate?
- Given below are two statements: L ∧ L = ϕ Statement I : The problem "Is 1 2 ? " is L undecidable for context sensitive languages 1 L and 2.…
- Consider the following grammars : G : S → aSb|bSa|aa 1 G : S → aSb|bSa|SS ∣ λ 2 G : S → aSb|bSa|SS ∣ a 3 G : S → aSb|bSa|SS|SSS|λ 4 Which o…
- Which grammar generates L = {aⁿbⁿ⁻³ | n > 2} over Σ = {a, b}?