1
$\begingroup$

The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic expressions", each looking like a string of variables to which pairs of balanced parentheses are multiply applied in an exhaustive manner (that is, you cannot insert yet another pair of parentheses).

Is there a grammar which defines this language? (I am a novice in formal languages and I am not sure my question is correctly formulated)

$\endgroup$
1
  • $\begingroup$ Isn't it a very simple one, just symbols and binary application? $\endgroup$ – Andrej Bauer Jan 27 at 11:46
1
$\begingroup$

The set of valid expressions in combinatory logic forms a computable formal language, and so can be described by a grammar. It is likely that this language is context-free, and so can be described by a context-free grammar.

More generally, we know the power of grammars exactly: a formal language can be described by a grammar if and only if it is recursively enumerable. So if there is an algorithm which enumerates all valid expressions in combinatory logic, then the language of all valid expressions in combinatory logic can be described by a grammar.

Even more generally, by definition, a formal language over an alphabet $\Sigma$ is just a collection of words over $\Sigma$. This means that any encoding of combinatory logic expressions which uses some fixed alphabet is automatically a formal language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.