Perplexinomicon

This is the first half of a proof that is the first question from the may qualifiers. Tougher to write up than I thought it would be.

Let L be the language defined by the following recursive definition:

1. Λ and b are in L
   
2. If x is in L, then axb and bxa are in L
   
3. If x and y are in L, then xy is in L
   
4. No other strings are in L
   

Give a simple non-recursive definition of L. Give a formal proof that your answer is correct.

2  Solution

To be proved: L = A.

This will be proved in two steps.

1. 
   L ⊂ A
   
2. A ⊂ L
   

Proof.L ⊂ A

We proceed by structural induction. Note that for a string x, |a|_x is the positive integer number of as in x.

Basis Step: Λ and b are in A. This is obvious, both are strings over {a,b}* | |b|≥|a|

Induction Hypothesis x, y ∈ A

Statement to be shown in induction step: xy, axb, bxa ∈ A, that is, applying any production rule for L to a string in A produces another string in A.

Proof of induction step:

We know that for x, |a|_x ≤ |b|_x and for y, |a|_y ≤ |b|_y. By the rules of concatenation, xy has |a|_x+|a|_y, |b|_x+|b|_y.
By properties of integers, |a|_x+|a|_y ≤ |b|_x+|b|_y, so xy ∈ A

x has |a|_x ≤ |b|_x by definition. axb or bxa both form new strings with the property that |a| = |a|_x+1, |b|=|b|_x+1. By properties of integers, |a| ≤ |b| → |a|+1 ≤ |b|+1

Therefore xy, axb, bxa are all in A, and L ⊂ A, as was to be shown.

This document was translated from L^AT_EX by
H^EV^EA.