Do all logics have formula syntax specified by context-free grammar?

550 Views Asked by At

I think propositional logic formulas syntax could be specified by context-free grammar with production rule below, where $A$ generates a finite string of $a_0, a_1$ stands for an atomic formula variable.

$$S \to\,\, \sim\!\! S \mid ( S \& S ) \mid A$$ $$A \to\,\, Aa_0 \mid Aa_1 \mid \epsilon$$

Are there any other kinds of logic that have formulas syntax that couldn't be specified by context-free grammar?

edit: Edited the CFG production rules for propositional logic to produce a countable infinite number of atomic formula variables.

edit2: Rewording the question as "Do all logics have formula syntax specified by context-free grammar?"

1

There are 1 best solutions below

3
On BEST ANSWER

Well, I would say that any "usual" logic can be specified by a context free grammar.

however there is no restriction in the definition of a logic for example let me introduce you the Wece logic defined as follow: $\phi$ is a formula of the wece formula if and only if it can be written as $\psi\psi\psi$ where $\psi$ is a formula of propositional logic.

The evaluation of $\phi$ is given as the evaluation of $\psi$ in propositional logic.

This logic (totally useless) is well define but not context free.

(sorry I didn't think of any better example, I don't remember having stumbled on a non context free defined logic ever).