Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Exercise sheet 1

Words and languages

Prefixes, factors and subwords, products and stars of languages, and a few identities to prove or disprove. Chapter 1.

Unless stated otherwise, $\Sigma = \{a, b\}$.

Solution
  1. Prefixes: $\varepsilon, a, ab, aba, abab$. Suffixes: $\varepsilon, b, ab, bab, abab$. Factors: $\varepsilon, a, b, ab, ba, aba, bab, abab$ (eight; $ab$ appears twice in $u$ but counts only once).
  2. $\varepsilon$; $a, b$; $aa, ab, ba, bb$; $aab, aba, abb, bab$; $abab$. Twelve subwords. The missing words of length 3 ($aaa$, $baa$…) would require three $a$, or a $b$ before two $a$.
  3. Yes for prefixes: one per length, from 0 to $n$. No for subwords: there are $2^n$ ways of choosing the letters to keep, but different choices can give the same word (here, 12 subwords for $2^4 = 16$ choices). As soon as a letter appears twice, keeping one or the other of its occurrences gives the same subword: there are exactly $2^n$ subwords if and only if the letters of the word are all different. Over $\{a, b\}$, this only happens for $n \leq 2$ ($ab$ does have 4 subwords).
Solution
  1. $L_1 L_2 = \{a, ab, abb\}$; $L_2 L_1 = \{a, ab, ba, bab\}$; $L_1^2 = \{aa, aab, aba, abab\}$.
  2. Three words: $ab$ is obtained twice, as $a \cdot b$ and as $ab \cdot \varepsilon$. The product is a set, duplicates disappear.
  3. $abab = ab \cdot ab$: yes. $aba = ab \cdot a$: yes. $abba$: no. Every word of $L_1$ starts with $a$, so every $b$ of a word of $L_1^*$ is preceded by an $a$ or is part of $ab$; $bb$ cannot appear.
Solution
  1. False: $L \cdot \emptyset = \emptyset$ ($\emptyset$ is absorbing). Counterexample: $L = \{a\}$.
  2. True: $u\varepsilon = u$ for every $u$.
  3. True. $L^* \subseteq L^*L^*$ (take $\varepsilon$ in the second factor); and two sequences of words of $L$ put end to end make one, so $L^*L^* \subseteq L^*$.
  4. False: $L_1 = \{a\}$, $L_2 = \{b\}$. $abab \in (L_1L_2)^*$ but not in $a^*b^*$; and $aab \in a^*b^*$ but not in $(ab)^*$.
  5. False: with the same ones, $ab \in \{a, b\}^*$ but $ab \notin a^* \cup b^*$.
  6. True: a factorisation into words of $L_1$ is a factorisation into words of $L_2$.
  7. False in general: if $\varepsilon \in L$, then $\varepsilon \in L^+$. Counterexample: $L = \{\varepsilon\}$, $L^+ = \{\varepsilon\}$ and $L^* \setminus \{\varepsilon\} = \emptyset$. It is true if $\varepsilon \notin L$.
Solution
  1. The words that contain at least one $a$.
  2. The words that contain an even number of $a$: some $b$, then blocks of two $a$ separated and followed by $b$.
  3. The words that do not contain the factor $aa$: every $a$ is followed by a $b$, except possibly a final $a$.
  4. The words of even length.
Solution
  1. $f(0) = 1$ ($\varepsilon$), $f(1) = 2$, $f(2) = 3$ ($ab$, $ba$, $bb$), $f(3) = 5$ ($aba$, $abb$, $bab$, $bba$, $bbb$).
  2. A word of length $n \geq 2$ without $aa$ starts either with $b$, followed by any word without $aa$ of length $n - 1$; or with $a$, and then the next letter must be $b$, followed by any word without $aa$ of length $n - 2$. The two cases are disjoint.
  3. $f(4) = 8$, $f(5) = 13$, $f(6) = 21$. It is the Fibonacci sequence, shifted.