The meaning of $\ast$ in $\{0,1\}^\ast$ and of $\lambda$ such that $\forall x\in\{0,1\}^\ast$ we have $\lambda x=x$.

Question

I have the following homework problem.

(a) Prove by structural induction that for all $x ∈\{ 0 , 1 \} ^∗$ , $λx = x$.

(b) Consider the function reverse : $\{ 0 , 1 \}^∗ → \{ 0 , 1 \} ^∗$ which reverses a binary string, e.g, reverse $(01001) = 10010$. Give an inductive definition for reverse . (Assume that we defined { 0 , 1 } $^∗$ and concatenation of binary strings as we did in lecture.)

(c) Using your inductive definition, prove that for all $x,y ∈ \{ 0 , 1 \} ^∗$ , reverse ($xy$) = reverse ($y$) reverse ($x$). (You may assume that concatenation is associative, i.e., for all $x,y,z ∈ \{ 0 , 1 \} ^∗$ , $x ( yz ) = ( xy ) z$ .

I understand how to do (c), but do not understand what "$\{ 0 , 1 \} ^∗$" is (specifically I don't understand what the asterisk denotes, otherwise I would assume it is just the set containing 1 and 0) and what "$λ$" is. Most of my questions about (a) and (b) stem from these misunderstandings.

Any help would be appreciated.

Answer 1

The asterisk is the Kleene star and $\lambda$ is the empty word. The latter is more commonly denoted by $\varepsilon$. Some authors use $1$ as well (especially when considering, say, $X^*$ as a monoid for some set $X$, under concatenation).