Consider L = {ab, aa, baa}. Which string is NOT in L*?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. baaaabaaaaa
Explanation
In baaaabaaaaa the first b must start 'baa'; then 'aa'; the second b can start 'baa' (leaving 'aaa', odd) or end 'ab' (leaving a single 'a' before it). Neither splits completely, so it is not in L*. The others split, e.g. ab·aa·baa·ab·aa.
More Theory of Computation and Compilers questions
- Consider the NPDA ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)}, δ(q0, a, z) = {(q1, 11z)}, δ(q1, a, 1) = {(q…
- Consider two PCP instances over {0, 1}, each with lists A and B of three strings. X: A = (1, 10111, 10), B = (111, 10, 0). Y: A = (10, 011,…
- Match List I with List II. List I: (A) Activation record, (B) Location counter, (C) Reference count, (D) Address relocation. List II: (I) L…
- Consider the grammar S → SbS | a. The string abababa has (A) two parse trees (B) two leftmost derivations (C) two rightmost derivations. Wh…
- Match List I with List II. List I: (A) Type 0, (B) Type 1, (C) Type 2, (D) Type 3. List II: (I) Finite automata, (II) Turing machine, (III)…
- Statement I: The LALR parser is more powerful than the canonical LR parser. Statement II: The SLR parser is more powerful than LALR. Which…