Hacker News new | ask | show | jobs
by thylacine222 1305 days ago
No, anything describable in BNF is at most as high on the Chomsky-Schutzenberg hierarchy as context-free grammars, regardless of size. BNF is also not a normal form, so you can't really compare rules written in BNF to one another that way. There is Chomsky Normal Form, which you could use to compare sizes. But natural languages have been shown to be non-context-free, so they aren't describable in CNF.

You might be thinking of the notion of MDL (minimum description length), which is an information-theoretic notion of complexity which boils down to the question "how long is the program that generates this data". To use minimum description length, however, you need to have a fixed programming language. So if you have a Python program that generates all of English and all of Japanese, then you could compare the complexity of those two languages.

However, this measure of complexity can't be stated absent the assumption that these languages are generated using Python -- that is, the fact that language A is more complex than language B in Python does not entail that language A is more complex than language B in the mind (using the "mind's programming language").

And herein lies the big question for a lot of linguists: what's the programming language that the mind uses to generate language?