⟸ Go Back ⟸
Exercise 4 (Homework 1).
(Kleene star, theory of languages)

Characterizations

Justify your answers to the following questions. Languages are taken over a fixed alphabet.

  1. When is a language equal to its positive closure? Does L=L^+ hold if and only if L^2\subseteq L?
  2. 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^*?
  3. 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?
  4. 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?

Remember that if P and Q are two statements such that P implies Q, then P is said to be a sufficient condition for Q, while Q is said to be a necessary condition for P. In addition, P is called a characterization of Q when P is both a necessary condition and a sufficient condition for Q.