1

If we have a language $L$ defined over the alphabet ${(,)}$ defined by

  1. $\epsilon \in L$
  2. If $X \in L$ and $Y \in L$ then $XY \in L$
  3. 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?

Enthuziast
  • 155
  • 2
    Assume that all words of length smaller than $n$ have an even number of characters. Let $Z\in L$ have $n$ character. Then either there are $X,Y\in L$ such that $Z=XY$ or there is $X\in L$ such that $Z=(X)$. In the first case $X,Y$ have less than $n$ characters. Therefore, by assumption they have even number of characters. Then $XY$ has also even number of character. Similarly in the case $Z=(X)$, $X$ has $n-2<n$ characters and therefore and enve number. Then so does $Z$. –  Feb 29 '20 at 20:30
  • Thanks @flan ! But couldn't there then be a counter-example where for example X could be a one-character-word? – Enthuziast Feb 29 '20 at 20:57
  • 1
    Supposedly $L$ is the smallest language satisfying the rules above. By the way, I assumed that $\lambda$ is your notation for the empty word. In other places people use $\epsilon$ for it. Now, if $X$ has one character, then it is not $\lambda$. Then it would have to be formed using either rule (2) or rule (3) from smaller words. –  Feb 29 '20 at 21:03
  • Thank you again, @flan for your patience. Yes; by $\lambda$ I meant the empty word. Edited for not confusing others. Wouldn't we be able to form the letter "a", "b" and "ab" from rule (2), thus having an example of odd-numbered words? – Enthuziast Mar 01 '20 at 06:52
  • 1
    Yes, if you postulate that a one-character word "a" is in $L$, then some odd-character words will be in the language. The thing is that people say "The language defined by the rules ..." they mean the smallest language satisfying those rules or another way to look at it the words that are inductively created exclusively by those rules. –  Mar 01 '20 at 11:13

1 Answers1

1

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.

Henno Brandsma
  • 242,131