Pre-Midterm #1 Review

Mark all correct answers in each of the following questions. Σ denotes an arbitrary alphabet unless otherwise specified.

1. (a) If u is an arbitrary word in Σ^{∗}, then there exist infinitely many words v ∈ Σ^{∗} for which uv = vu. These are exactly the words of the form v = u^{n} for some n ≥ 0.

(b) If u is an arbitrary word in Σ^{∗}, then every word v of the form v = u^{n} satisfies uv = vu, and there exist no other words v satisfying this equality.

(c) If u is an arbitrary word in Σ^{∗}, then every word v of the form v = u^{n} satisfies uv = vu. There exist words u, for which these are the only words commuting with u, but there exist words u, for which there are infinitely many additional words v commuting with u.

(d) There exists an alphabet Σ such that every u, v ∈ Σ^{∗} satisfy uv = vu.

(e) There exists an alphabet Σ such that uv ≠ vu for every u, v ∈ Σ^{∗} − {ε}.

(f) None of the above.

2. (a) The language consisting of all palindromes can be given a finite description, and hence it is regular.

(b) If a language L contains only palindromes, then it is countable and therefore finitely describable.

(c) If a language L contains infinitely many palindromes and infinitely many non-palindromes, then it is not regular, and hence it is uncountable.

(d) If a language L contains infinitely many palindromes and infinitely many non-palindromes, then it is countable and regular.

(e) None of the above.

3. Let Σ = {0, 1} and L = {01, 10}^{∗}. Then:

(a) L consists of all words of even length over Σ.

(b) L is contained in the language consisting of all words of even length over Σ.

(c) L is contained in the language consisting of all words of even length over Σ in which any two consecutive letters are distinct.

(d) L is infinite, and every word in it is of even length.

(e) None of the above.

4. (a) For every language L we have (L ⋃ L^{2})^{∗} = L^{∗}.

(b) The equality (L ⋃ L^{2})^{∗} = L^{∗} is impossible if L contains non-empty words.

(c) There exists a language L ≠ ∅ for which (L ⋃ L^{2})^{∗} ⋂ L^{∗} = ∅.

(d) For every language L we have (L ⋃ L^{2})^{∗} ⊇ L^{∗} − L.

(e) None of the above.

5. Let M = ({q_{1}, q_{2}, q_{3}}, {a}, Δ, q_{1}, {q_{1}}), where Δ = {(q_{i}, a, q_{j}) : i, j ∈ {1, 2, 3}, i ≠ j}. Then:

(a) L(M) = {a}^{∗}.

(b) L(M) = {a^{2}}^{∗} ⋃{a^{3}}^{∗}.

(c) L(M) = {a}^{∗} − {a}.

(d) L(M) = {a^{2}}^{∗}{a^{3}}^{∗}.

(e) L(M) strictly contains {a^{2}}^{∗}{a^{3}}^{∗}.

(f) None of the above.

6. Let M_{1} = (Q_{1}, Σ, Δ_{1}, s_{1}, A_{1}) , M_{2} = (Q_{2}, Σ, Δ_{2}, s_{2}, A_{2}) , be two NFA’s. Suppose there exists a surjective mapping f : Q_{1} ⟶ Q_{2} such that s_{2} = f(s_{1}) and Δ_{2} = {(f(q), w, f(p)) : (q, w, p) ∈ Δ_{1}}. Then:

(a) If A_{2} = f(A_{1}), then L(M_{2}) = L(M_{1}).

(b) If A_{2} ⊇ f(A_{1}), then L(M_{2}) ⊇ L(M_{1}).

(c) If f is injective, then L(M_{2}) = L(M_{1}) if and only if A_{2} = f(A_{1}).

(d) If f is injective and A_{2} = f(A_{1}), then L(M_{2}) = L(M_{1}).

(e) None of the above.

Solutions

1. Words of the form v = u^{n} always commute with u as uv = u^{n+1} = vu. If u ≠ ε, then this already supplies infinitely many words commuting with u. If u = ε, then every word v commutes with u. Hence in any case there exist infinitely many words commuting with u. Now, if u is not a proper power of another word (as is any word of the form a^{k}b for some k ≥ 1), then only powers of u commute with u. However, if u is a proper power of another word, say u = w^{k} for some w ≠ ε and k ≥ 2, then u commutes with every word of the form w^{n}. Since w^{n} is not a power of w^{k} unless k | n, this provides infinitely many words commuting with u which are not powers of u.

If Σ is a one-letter alphabet, then any two words in Σ^{∗} commute.

Thus, only (c) and (d) are true.

2. Regular expressions are but one way of forming languages. Hence, the fact that the language consisting of all palindromes admits a finite description does not imply that it is regular. The language of all palindromes is infinite, and therefore there exist uncountably many languages consisting solely of palindromes. Since the family of all finitely describable languages is countable, “most” languages consisting only of palindromes are not finitely describable. If |Σ| ≥ 2, then Σ^{∗} contains infinitely many palindromes and infinitely many non-palindromes, yet Σ^{∗} is regular. The family of languages containing both infinitely many palindromes and infinitely many non-palindromes is, in case |Σ| ≥ 2, uncountable, and consequently contains non-regular languages.

Thus, only (e) is true.

3. L is formed by concatenating words with two letters, so that all words in L are of even length. The word 00 certainly does not belong to L, and therefore not every word of even length belongs to L. The word 0110 does belong to L, so that consecutive letters in words of L are not necessarily distinct. Since all words of the form (01)^{n} belong to L, the language L is infinite.

Thus, only (b) and (d) are true.

4. Since L ⊆ L ⋃ L^{2}, we have L^{∗} ⊆ (L ⋃ L^{2})^{∗}. On the other hand, L^{∗} ⊇ L ⋃ L^{2}, and therefore L^{∗} = (L^{∗})^{∗} ⊇ (L ⋃ L^{2})^{∗}. Since ε belongs to L_{1}^{∗} for any language L_{1}, we cannot have (L ⋃ L^{2})^{∗} ⋂ L^{∗} = ∅ (even if L = ∅).

Thus, only (a) and (d) are true.

5. Obviously, both words a^{2} and a^{3} belong to L(M). It follows that L(M) ⊇ {a^{2}, a^{3}}^{∗}. The language on the right hand side consists of all words of the form a^{n} with n ≠ 1.

Thus, only (c) and (d) are true.

6. The condition A_{2} = f(A_{1}) does not guarantee that L(M_{2}) = L(M_{1}). For example, if Q_{2} contains a single state, the automata are deterministic and A_{1} ≠ ∅, then L(M_{2}) = Σ^{∗}, while L(M_{1}) is in general not Σ^{∗} (and may actually be empty). However, as long as A_{2} ⊇ f(A_{1}), every word accepted by the first automaton is clearly accepted by the second, and hence L(M_{2}) ⊇ L(M_{1}). If f is injective and A_{2} = f(A_{1}), then the two automata are actually the same, and in particular L(M_{2}) = L(M_{1}). However, it may happen that A_{2} ≠ f(A_{1}), and yet L(M_{2}) = L(M_{1}). As an example, suppose A_{1} = ∅, while A_{2} consists of several states to which it is impossible to get in any way when starting from s_{2}. In this case L(M_{2}) = L(M_{1}) = ∅, although A_{2} ≠ f(A_{1}) = ∅.

Thus, only (b) and (d) are true.