[FOM] Formal grammar question
urquhart at cs.toronto.edu
Wed Nov 9 09:30:30 EST 2005
In answer to Allen Hazen's query about Polish notation --
there is a simple algorithm to check if a string of symbols
is well-formed, in prefix notation.
Assign the number -1 to constants and variables,
and the number k to (k+1)-place operators.
Now proceed from left to right along the string,
adding the numbers associated with symbols as you go.
The string is well-formed if and only if it satisfies the
All of the partial sums are non-negative, except for the
last, which is -1.
I believe that this algorithm was already known to the
Polish logicians before the war, and if I recall correctly,
it is given for 2-place operators in Lukasiewicz's
paper on the logic of equivalence from 1939.
The general case is given in the last chapter of
Rosenbloom's book "Elements of Mathematical Logic",
Dover 1950, where it is attributed to Karl Schröter.
More information about the FOM