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

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.

• After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark $\checkmark$ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?, What should I do if someone answers my question?. Mar 12, 2020 at 20:24
• Also, please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. Mar 12, 2020 at 20:24

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