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.
Best Answer
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).