4
$\begingroup$

Leslie Lamport claims that TLA+ is too complex to be described in BNF.

Does that mean TLA+ is not a context free language?

What is the relationship between the set of context free languages and the set of languages that can be described by BNF grammars?

$\endgroup$
1
  • $\begingroup$ "TLA+ is too complex to be described in BNF" this is an ambiguous sentence. Placed in a research article it might well mean "TLA+ is not context-free", written as an answer to the question "where can I find the BNF grammar" it is just a shorthand for "TLA+ is too complex to be described in BNF (by a human hand)", i.e. we did not spend the time & energy to do it. $\endgroup$ – Bakuriu Apr 24 at 14:47
19
$\begingroup$

No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means.

It might not be convenient to write the grammar. For example, consider the language of words containing characters from some alphabet where no word contains two of the same character. The language is context-free, but the size of the shortest BNF grammar which describes it is exponential in the size of the alphabet. If you chose the set of 95 printable ASCII characters, the grammar would have so many productions that you would need a computer the size of the galaxy to store them.

Even if the language is not so pathological, you might feel that writing down its grammar in BNF is too time-consuming and mundane to make it a worthy use of your superior intellect.

But if the language is context-free, the grammar exists, at least in the mathematical sense of the word "exists".

$\endgroup$
0

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.