If we have a language $L$ defined over the alphabet ${(,)}$ defined by
- $\epsilon \in L$
- If $X \in L$ and $Y \in L$ then $XY \in L$
- If $X \in L$ then $(X) \in L$
I want to prove that there is an even number of characters in any $X \in L$.
The basis step in an induction proof is simple I guess, as the $X=\epsilon$ returns 0 characters.
I struggle with the induction step, however, as I feel that I create a circular reference. I have tried assuming that for any $X \in L$, the number of characters is even and showing that then also any $Y \in L$ must return an even number of characters. My reasoning is that since $X \in L$ and $Y \in L$ then $XY \in L$, and that $XY$ must be even-numbered and therefore also $Y$ must be even-numbered.
Any idea where my reasoning faults?
There are languages that satisfy 1,2 and 3 and that contain words of odd length (the simplest one is all strings from the alphabet...). But the smallest language that obeys 1,2 and 3 does have only strings of even length; this is probably what you mean by the language defined by these rules.
In that case you can assume that each word is in it, is because of rule 2 or 3, and then it's made from smaller even words in a parity preserving way : $X$ even implies $(X)$ even, and $X,Y$ even implies $XY$ even, both of which are obvious.