Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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".
