Exercise 1 (From informal to formal descriptions) Given an alphabet \Sigma, interesting languages L\subseteq \Sigma^* can be often written using the set notation as L=\{w\in \Sigma^* \mid P(w)\}, where P(w) is a predicate P defined on word w. For instance, the language L of all words over \{a,b\} that contain the subword ab can be denoted as
L=\{w\in \{a,b\}^* \mid \exists x,y\in \{a,b\}^*\ w=xaby\}.
Write the formal languages over \Sigma=\{a,b\} for the following informal descriptions of P(w):
To the right of every subword ab in w there is some subword ba.
Word w contains both the subword ab and the subword ba.
Between every two b’s in w there is some a.
Every occurrence of b in w is in an even position (the first symbol of a word is in position 1).
Word w has some prefix with at least as many b’s as a’s.
In every prefix of w, the number of b’s is at least the number of a’s.
Word w has some even-length prefix with at least as many b’s as a’s.
Every even-length prefix of w has at least as many b’s as a’s.
Word w has a prefix and a suffix of the same nonzero length, equal to each other, and strictly less than the length of the word.
Word w is a palindrome, that is, w reads the same forwards as backwards, e.g. madam or rotator in English.
Exercise 2 (Concatenation – basic properties) Justify your answers to the following questions. All words and languages are taken over a fixed alphabet.
Is the concatenation commutative? Does it hold xy=yx for all words x,y? Does it hold AB=BA for all languages A,B? Do your previous answers depend on the size of the alphabet?
Is the concatenation associative? Does it hold that x(yz)=(xy)z for all words x,y,z? Does it hold that A(BC)=(AB)C for all languages A,B,C? Do your previous answers depend on the size of the alphabet?
Does the cancellation law hold for concatenation of words? That is, does xy=xz imply y=z for all words x,y,z?
Does the cancellation law hold for concatenation of languages? That is, does AB=AC imply B=C for all languages A,B,C? What if we additionally impose that A\neq \emptyset, does it hold now?
Condition for a double equality. Given languages A,B,C,D such that A,B are non-empty, AB=CD, and all words in A and C have the same length, does it hold that A=C and B=D?
Does concatenation of languages distribute over union? That is, for all languages A,B,C, does it hold that (A\cup B) C=AC\cup BC and A(B\cup C)=AB\cup AC? What if instead of “=” we only ask for “\subseteq” or “\supseteq”, does it hold now?
Does concatenation of languages distribute over intersection? That is, does it hold that (A\cap B) C=AC\cap BC and A(B\cap C)=AB\cap AC for all languages A,B,C? What if instead of “=” we only ask for “\subseteq” or “\supseteq”, does it hold now?
Exercise 3 (Kleene Star – basic properties) Justify your answers to the following questions. Languages are taken over any fixed alphabet.
Does the Kleene star distribute over concatenation of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*L_2^*= (L_1L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”? What if we impose L_1=L_2, does it hold now? And what if, when L_1=L_2, instead of “=” we only asked for “\subseteq” or “\supseteq”?
Do positive closures always induce nontrivial partitions? That is, for every two languages L_1,L_2, if L_1^+\cup L_2^+=\{a,b\}^+ and L_1^+\cap L_2^+=\emptyset, then either L_1=\emptyset or L_2=\emptyset.
Does the Kleene star distribute over union of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cup L_2^*= (L_1\cup L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
Does the Kleene star distribute over intersection of languages? That is, for every two languages L_1,L_2, does it hold that L_1^*\cap L_2^*= (L_1\cap L_2)^*? What if instead of “=” we only asked for “\subseteq” or “\supseteq”?
Is the Kleene star monotone w.r.t. inclusion? That is, for every two languages L_1,L_2, does L_1\subseteq L_2 imply L_1^*\subseteq L_2^*? Does the converse hold? That is, for every two languages L_1,L_2, does L_1^*\subseteq L_2^* imply L_1\subseteq L_2? What if L_1=\{a,b\} and L_2 is a language over \{a,b\}, does the converse hold in this special context?
Chain of inclusions. Does it hold for every language L that \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? What if we reverse the inclusions? Does \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^* hold?
Sufficient condition for distinct Kleene stars. Does L_1\cap L_2=\emptyset for two languages L_1, L_2 \not=\emptyset imply L_1^*\not=L_2^*?
Where is the positive closure squared? Does L^+L^+\subseteq L^+ hold for every language L? Does the reverse inclusion L^+L^+\supseteq L^+ hold?
Exercise 4 (Characterizations) Justify your answers to the following questions. Languages are taken over a fixed alphabet.
When is a language equal to its positive closure? Does L=L^+ hold if and only if L^2\subseteq L?
When is a language equal to its Kleene star? Is L^2\subseteq L a necessary condition for the equality L= L^*? Is \lambda \in L a necessary condition for L= L^*? Which logic combination (\land, \lor, …) of the statements L^2\subseteq L and \lambda\in L constitutes a necessary and sufficient condition for the equality L= L^*?
When is a language included in its square? Is \lambda\in L a sufficient condition for the inclusion L\subseteq L^2? Is L = \emptyset a sufficent condition for L\subseteq L^2? Which logic combination (\land, \lor, …) of the statements L = \emptyset and \lambda\in L constitutes a sufficient and necessary condition for the inclusion L\subseteq L^2?
When does a language equal its square? Is L=L^* a sufficient condition for the equality L= L^2? Is L = \emptyset a sufficent condition for L= L^2? Which logic combination (\land, \lor, …) of the statements L = L^* and L=\emptyset constitutes a sufficient and necessary condition for the equality L= L^2?
Exercise 5 (Reverse – basic properties) Justify your answers to the following questions.
The reverse of the concatenation (1). Show that for any two words x,y, (xy)^R=y^Rx^R. Does the analogue property hold for languages? That is, given languages L_1,L_2, does it hold that (L_1L_2)^R=L_2^RL_1^R?
The reverse of the concatenation (2). Is it true that, given two languages L_1,L_2 such that (L_1L_2)^R=L_1^R L_2^R, then necessarily L_1=L_2?
Does the reverse distribute over union? That is, given languages L_1,L_2, does it hold that (L_1\cup L_2)^R=L_1^R\cup L_2^R?
Does the reverse distribute over intersection? That is, given languages L_1,L_2, does it hold that (L_1\cap L_2)^R=L_1^R\cap L_2^R?
Does taking the complement and the reverse of a language commute? That is, it is true that \overline{L}^R=\overline{L^R}?
Does taking the Kleene star and the reverse of a language commute? That is, it is true that (L^*)^R=(L^R)^*?
Exercise 6 (Homomorphisms I – basic properties) Let \sigma :\Sigma^* \to \Sigma^* be a function. Which of the following definitions of \sigma define a homomorphism? That is, which ones satisfy that for any words x,y\in \Sigma^*, \sigma(xy)=\sigma(x)\sigma(y)? Let w=a_1a_2\cdots a_n \in \Sigma^*, where a_1,a_2,\dots, a_n \in \Sigma.
\sigma(w)=a_1a_1a_2a_2\cdots a_na_n.
\sigma(w)=a_1a_2a_2a_3a_3a_3\cdots\overbrace{a_n\cdots a_n}^{n)}.
\sigma(w)=ww.
\sigma(w)=w.
\sigma(w)=\lambda.
\sigma(w)=a^{|w|}, where a\in \Sigma.
\sigma(w)=w^R.
\sigma(w)=\sigma_1(\sigma_2(w)), where \sigma_1,\sigma_2 are homomorphisms.
Exercise 7 (Homomorphisms II – basic properties) Given a morphism \sigma:\Sigma^*\to\Sigma^* and languages L,L_1,L_2\subseteq \Sigma^*, justify your answers to the following questions.
Does homomorphism on languages distribute over concatenation? That is, does it hold that \sigma(L_1L_2)=\sigma(L_1)\sigma(L_2)?
Does homomorphism and exponentiation of languages commute? That is, does it hold that \sigma(L^n)=\sigma(L)^n for any positive integer n?
Does homomorphism and union of languages commute? That is, does it hold that \sigma(L_1\cup L_2)= \sigma(L_1)\cup\sigma(L_2)?
Does homomorphism of languages and the Kleene star commute? That is, does it hold that \sigma(L^*)=\sigma(L)^*?
Does homomorphism and reverse of languages commute? That is, does it hold that \sigma(L^R)=\sigma(L)^R?
Does homomorphism and complementation of languages commute? That is, does it hold that \sigma(\overline{L})=\overline{\sigma(L)}?
Does the identity homomorphism on a language act as the identity on its words? That is, does it hold that whenever \sigma(L)=L, then \sigma(x)=x for all x in L?
Exercise 8 (On the size of languages) Justify your answers to the following questions.
Given two languages L_1,L_2, is it true that |L_1|\cdot|L_2|=|L_1\cdot L_2|? What if L_1=L_2?
Given a homomorphism \sigma, is it true that if \sigma is injective then |\sigma(L)|=|L|?
Given a language L, is it true that |L^R|=|L|?
Given a language L and a positive integer n, is it true that |L^n|=|L|^n?
Exercise 9 (Shifting a language) Given a language L, we define the shift of L, denoted S(L), as the language that contains the words obtained by applying a circular shift to each word in L in all possible ways; formally, S(L) = \{vu\mid uv\in L\}. Argue whether the following statements are true (with a justification) or false (with a counterexample) for any L.
S(L)^*\subseteq S(L^*).
S(L)^*\supseteq S(L^*).
\overline{S(L)}=S(\overline{L}).
S(L^R)=S(L)^R.
S(L_1\cup L_2)=S(L_1)\cup S(L_2).
S(L_1\cap L_2)=S(L_1)\cap S(L_2).
S(L_1L_2)=S(L_1)S(L_2).
S(\sigma(L))=\sigma(S(L)), where \sigma is a homomorphism.
Exercise 10 (Simplification of languages) Prove the following equalities between languages:
\{w\in \{a,b\}^* \mid aw=wb\}=\emptyset.
\{w\in \{a,b\}^* \mid abw=wab\}=\{ab\}^*.
Warning\{ab\}^* is not a typo, there is no “,” between a and b.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_a\}=\{w\in \{a,b\}^*\mid |w|_a\in 2\mathbb N\}.
\{xy\in \{a,b\}^* \mid |x|_a=|y|_b\}=\{a,b\}^*.
\{xy\in \{a,b\}^* \mid |x|_{aa}=|y|_b\}=\{a,b\}^*.
\{w\in \{0,1\}^* \mid \mathtt{value}_2(ww^R)\in 3\mathbb N\}=\{0,1\}^*
Exercise 11 (L=\overline{\Sigma L}) Prove that, for every alphabet \Sigma, there is a unique language L such that L=\overline{\Sigma L}. What is this language?
Give an alternative expression for L. Does L contain the empty word \lambda? If a word in L is of the form aw, with a\in \Sigma, is w in L or in \overline L? Once obtained the new expression, rewrite it as a function of L and resolve the recurrence relation.
Exercise 12 (Arbitrary long walks in graphs) Given a directed graph G (with loops) with n vertices, and two vertices s, t in it, show that if there exists a walk in G from s to t of length > n then there are arbitrary long walks from s to t. In other words that there exists an n_0\in \mathbb N such that for every m\geq n_0 there is a walk in G from s to t of length \geq m.
Exercise 13 (Easy induction) Let f: {\mathbb N} \rightarrow \mathbb N be a function such that f(x+y) = f(x)+f(y) for any x, y \in \mathbb N. Prove that for any x \in \mathbb N, f(x) = f(1) \cdot x.
Exercise 14 (Divisibility in number set) Prove that any set of n+1 positive integers less than or equal to 2n, where n \ge 1, contains two distinct elements a and b such that a divides b.
A possibility is to use the pigeonhole principle: the pigeons are the n+1 numbers and the holes are the odd numbers between 1 and 2n. A pigeon of the form 2^k d with d odd flies to hole d.
Another option is to consider an induction proof on n and distinguish two cases in the inductive step: at least one of the elements 2n+1 and 2n+2 is not in the set or both are.