[FOM] Formal grammar question

[A.P. Hazen]

Stupid, stupid, me!
In yesterday's post I asked  about the formal grammar (or 
computational complexity) aspects of parenthesis-free, "Polish," 
notation.
Well-formedness of Polish propositional formulas, like that of 
formulas in traditional (parentheses and infix operators) notation, 
is recognizable by a push-down automaton making a single, one-way, 
pass through the candidate string.  For simplicity, assume that all 
operators are binary: then a well-formed  formula  will contain one 
more atom than operator, and no initial segment of it will contain 
more  atoms than operators.  So, starting from the left, the 
automaton will  "push" (add 1 to its pushdown stack) when it gets to 
an operator, "pop" (subtract 1) when it gets to an atom, and accept 
iff it reaches the right end with 1 in its stack, never having read 
an atom with 0 in ist stack.
     This can be converted straightforwardly into a definition of WFF 
in terms of the basis of Goodman and Quine's 1947 article.
     (I've been trying to figure out whether there is something of 
mathematical interest in their article, given that the philosophical 
project that motivated them  has since been generally dismissed -- 
even by Quine in later writings -- as misguided.  It comes as a 
relief that they at least aren't depending on special features of the 
conventional notation!)
    (Thanks to Charles Silver for off-forum note on this.)
---
Allen Hazen
Philosophy Department
University of Melbourne