L is the lowest set of string under the following rules:
1) 1 $\in$ L
2) If x $\in$ L, 0x $\in$ L
3) If x $\in$ L, x0 $\in$ L
4) If x $\in$ L and y $\in$ L, x1y
Demostrate by induction that a string w $\in$ L iff has an odd number of 1s.
to right: The base is trivial but i dont know how to present an easy hypothesis to prove my tesis. I have to use the 4th rule to the induction step.
to left: ideas plz
To use structural induction, you have to show that if a string $s \in L$ and has the desired property, then the new string constructed by steps (2),(3) and (4) will also be in $L$ and satisfy the given property.
Induction hypothesis: Let $s,t$ be strings in $L$ such that $s,t$ have the desired property, i.e. both $s$ and $t$ have an odd number of $1'$s.
By step (2), $s \in L \implies 0s \in L$. The number of $1'$s in the string $0s$ is the same as the number of $1'$s in $s$ (which is odd by IH). Thus the number of $1'$s in the new string is also odd.
Step(3) is similar, so you can complete that.
By step (4), $s,t \in L \implies s1t \in L$. The number of $1'$s in the new string is $$1+\text{# of $1'$s in $s$}+\text{# of $1'$s in $t$}.$$
By IH, the number of $1's$ in both $s$ and $t$ are odd, say $n_s=2k+1$ and $n_t=2l+1$, then the number of $1'$ in the new string is $1+(2k+1)+(2l+1)=2(k+l+1)+1$, which is an odd number.
Thus the new string constructed by each constructor step will also have the same property.