Given a formal system[of 4 symbols: 0, 1, ( , ) ] with rules:
You may write down 0 or 1 at any time.
if strings s and t have been written down, you may write down (st).
write ⊢s to mean that s can be derived(written down) using these rules finitely many times, for example ⊢(10) or ⊢(00).
Part (a) was proving that if ⊢s then s contains the same number of occurrences of the symbol "(" as the symbol ")". Was done easily by induction.
Part (b), which I'm stuck on, asks to show that if ⊢s and p is an initial part of s which is not the empty string, nor the whole of s then p contains at least one more occurrence of the symbol "(" as of the symbol ")".
I've thought about using induction to prove the last letter of s will always be ")" but I can't think of a way to combine that with part (a) for a formal proof. Any help would be great thanks (:
We can do it by induction on the derivation.
Suppose ⊢(st), and that your property is true for s and t. Then, if p is an initial part of (st) as desired, several cases arise
if p = (, it is trivial.
if p = (q, where q is an initial part of s (non empty, non s), then by hypothesis, q contains at least one more ( than ), so (q contains at least two more (.
if p = (s, then as s contains the same number of ( and ), (s contains exactly one more (.
if p = (sq, where q is an initial part of t (non empty, non t), you can still conclude by induction hypothesis as in case (q.
if p = (st, then p contains exactly one more (.
I let you check the base cases.