First observation, as suggested, is that any wff $\alpha$ has the number of pairs of parentheses equal to the number of connective symbols. Let $S$ be the set of all sentence symbols, and $B\subseteq\overline{S}$ be the set of wffs such that the statement is true. Then, all sentence symbols are in $B$ , as such wffs have neither parentheses nor connective symbols. If $\alpha,\beta\in B$ , then $(\neg\alpha)$ adds one pair of parentheses and one connective symbol to the expression $\alpha$ , and $(\alpha\square\beta)$ adds one pair of parentheses and one connective symbol to the collection of parentheses and connective symbols found in both $\alpha$ and $\beta$ . In either case, the statement is true for the resulting wff, and $(\neg\alpha),(\alpha\square\beta)\in B$ , hence, by the induction principle, $B=\overline{S}$ .

Second observation is that every wff is either a sentence symbol or ends in a connective symbol followed by a sentence symbol followed by a series of right parentheses. Again, this is obviously true for sentence symbols, and then for $(\neg\alpha)$ and $(\alpha\square\beta)$ provided that it holds for $\alpha$ and $\beta$ . Therefore, by the induction principle, we conclude that this is true for all wffs.

Given these observations, if we form our building rules without right parentheses, then every wff (according to the new definition) will satisfy two new properties as follows: a) the number of left parentheses is equal to the number of connective symbols, and b) each wff is either a sentence symbol or ends in a connective symbol followed by a sentence symbol.

Accordingly, we modify Lemma 13A and Lemma 13B: for any wff, the number of left parentheses equals the number of connective symbols, and for any proper initial segment of wff that is the initial sentence symbol or that ends in a connective symbol followed by a sentence symbol the number of left parentheses is greater than the number of connective symbols (of course, this also implies that a proper initial segment cannot be a sentence symbol). Indeed, this is true for sentence symbols, and if this is true for $\alpha$ and $\beta$ , then this is true for $(\neg\alpha$ with such proper initial segments being $($ and $(\neg\alpha_{0}$ and for $(\alpha\square\beta$ with such proper initial segments being $($ , $(\alpha_{0}$ , $(\alpha$ and $(\alpha\square\beta_{0}$ .

Now, we modify the parsing algorithm accordingly. Namely, the last two steps are modified as follows. If the sub-expression being parsed is $(\neg\alpha$ , then we form a new leaf below it with the value $\alpha$ (note, that we do not need to check the right parenthesis here, as there are no, and that we exclude for the expression exactly one left parenthesis and one connective symbol from the very left of the expression, so that if our lemmas hold for $(\neg\alpha$ , they hold for $\alpha$ ). If the sub-expression being parsed is $(s$ such that $s$ does not start with $\neg$ , then either $s$ starts with a sentence symbol $A$ , in which case we set $\alpha=A$ , or we scan from the left all segments of $s$ ending in a connective symbol followed by a sentence symbol until we find an initial segment $\alpha$ such that $\alpha$ has exactly the same number of left parentheses and connective symbols. Then, as before, $\alpha$ must be followed by a binary connective symbol, i.e. there must by an expression $\alpha\square\beta$ (otherwise the algorithm halts), which forms two leaves with values $\alpha$ and $\beta$ . Similarly to the arguments in the text, the choice of $\alpha$ here is uniquely determined, as anything less does not have equal numbers of left parentheses and connectives, but anything bigger would have $\alpha$ as a proper initial segment either being a sentence symbol or ending in a connective symbol followed by a sentence symbol with equal numbers of left parentheses and connective symbols.

As an example, let as consider the expression given in the problem,$((A\wedge(\neg B\rightarrow(C\vee D$ . First parsing gives $\alpha=(A\wedge(\neg B$ . Note that $(A\wedge$ does not work as $\wedge$ is not followed by a sentence symbol, so that we do not even consider the substring $(A\wedge($ . Hence, we have two leaves, $(A\wedge(\neg B$ and $(C\vee D$ connected by $\rightarrow$ . Scanning of the first one gives two new leaves $A$ and $(\neg B$ , and the latter gives another leaf $B$ , while scanning of the second one gives two leaves $C$ and $D$ . This is the same tree, as we would have obtained using the textbook parsing algorithm on $((A\wedge(\neg B))\rightarrow(C\vee D))$ .