0

The background
The use of the context-free grammars in linguistics often prompts comparison with programming languages (e.g., see this question). Despite the formal structure similarities, I would like to argue that they serve very different goals and structured accordingly: the programming languages are about processing data, whereas the natural languages are about transferring/communicating the data.

In more expanded terms: the programming languages are characterized by limited syntax and vocabulary which however permit creating very complex data processing algorithms. (See, e.g., this article for some minimalist programming languages.)

On the other hand, the natural languages possess very extended vocabularies, whereas their syntax is aimed at organizing information rather than processing it.

Proposition
A more valid comparison is between the natural languages and the message encoding in information theory, where the syntax serves to communicate the largest amount of information using the smallest number of symbols with the smallest number of errors.

Question
Do you know about noisy channel coding theorem formulated in terms of CFGs? (In the standard textbooks it is presented in terms of Markov chains, which are equivalent to Regular grammars, i.e. the lower level in Chomsky hierarchy.)

Note to moderators
You are within your rights to close this question. It would be kind of you to propose migrating it, rather than simply shutting it down. In my opinion the question is a) most likely to get answers in this community and b) presents interest for people with linguistics background - which is why I chose to post it here.

Improve this question
8
  • 1
    I don't have an answer to your question, but you may find this paper interesting: aclweb.org/anthology/D08-1025.pdf
    – WavesWashSands
    Mar 3, 2020 at 9:43
  • 1
    I'll note, though, that most people in the field either stick to n-grams (which of course are basically higher-order discrete-time discrete-state MCs), or use RNNs (which are probably the best models we have, although they're unfortunately hard to understand).
    – WavesWashSands
    Mar 3, 2020 at 9:44
  • 2
    This question is about borrowing a theory from linguistics but applying it to something outside linguistics, so it does not belong here. My suggestion would be Computer Science or Theoretical Computer Science, both of which have many information theory questions.
    – curiousdannii ♦
    Mar 3, 2020 at 11:17
  • 1
    @curiousdannii: I actually see it as the opposite, borrowing something from outside linguistics (information theory, CFGs) with a view to applying it to natural language. i think its relevance on the site is quite marginal because it asks for a theorem rather than empirical applications, but given the natural language-related background, I decided to err on the side of not voting to close.
    – WavesWashSands
    Mar 3, 2020 at 11:23
  • 1
    @WavesWashSands I interpreted "Do you know about noisy channel coding theorem formulated in terms of CFGs?" as asking if anyone knows about noisy channel coding analysis using CFGs, rather than applying the NCCT to natural languages. But it's fine for us to disagree, and if the community thinks this belongs here, then that's fine.
    – curiousdannii ♦
    Mar 3, 2020 at 11:28

3 Answers 3

Reset to default
3

As I interpret your question, you propose an alternative theory of syntax to CFG for linguistics. It's a thought, but do you have any evidence? I didn't see any. Don't you think you should have some facts to go on if linguists are to forgo theories like GPSG, based on CFG. What facts of natural language support your view?

Improve this answer
1
  • I am not proposing a new theory. Rather I am saying that the analogy between the natural and the programming languages is a misleading one. The only basis for this analogy is the use of the CFGs. The analogy with message encoding is more appropriate, but less evident, since this topic is rarely discussed in terms of CFGs.
    – Roger V.
    Mar 3, 2020 at 21:14
1

The situation with natural languages is more convoluted because the analysis of sentences crucially depends on background knowledge, which makes use of metaphors, metonymy etc. widespread. Consider the sentence The Galway office called. The maximisation ("the largest amount of information") is achieved by compacting the sentence, i.e. leaving out what can be inferred (the technical term is abduction). Consequently, CFGs alone don't play a prime role in the transmission of information. In actual fact, ill-formed sentences can often be understood even when they lack structure (e.g. long time no see etc.) by simply inferring the intended meaning from the meanings of the individual words. That said, it would surely be interesting to investigate the noisy-channel approach taking abductive inference into account.

Improve this answer
3
  • 1
    I agree with the general idea of your answer, but surely there is no way that long time no see is ill-formed, or that its meaning is 'inferred' by putting together the individual words, at least for most people... It's a highly entrenched and conventionalised prefab in English.
    – WavesWashSands
    Mar 3, 2020 at 10:35
  • @WavesWashSands You are right, this is not a good example. The point is that it would be understood even if it weren’t an idiom — this is how it came about after all. A better example would be “children go now school” or something clearly ill-formed yet perfectly understandable. Thanks for pointing that out.
    – Atamiri
    Mar 3, 2020 at 10:46
  • long time no see could become an idiom only because there is structure and the phrase well formed. There are millions of noun phrases using the same scheme, all work, no play [makes jack a dull boy]. I really want to know what it's called. I used to think it's anapher, anaphora, but literature studies seems to require a rhyme schmyme for that, no pants, no serivce. The only odd thing is that a see is not usually a noun, but I hadn't joticed that should be a problem
    – vectory
    Mar 14, 2020 at 20:55
1

If you are thinking of formal language theory to compare programming languages and human languages, make sure you compare apples to apples. Don't mix up what a program can compute with what grammar rules the program text must follow.

To say that a language is in a given syntax class means that well-formed strings (a program) can be parsed using a grammar that has rules of restricted form.

For example, a program written in Pascal has a Backus-Naur (CFG) parser with extra rules for type checking which I think makes it formally a CSG. But the programs written in CSG can still compute (on an unbounded resource interpreter) Turing-complete problems. The language is restricted but the things the programs can compute are not. Forth, which is a language that manipulates machine numbers on a stack, is also Turing complete, but the language itself is a very simple regular language.

In a similar manner, the syntax of human languages are mostly regular, with embedding requiring some simple CFG rules, and maybe morphological agreement needing some CSG rules. But the concepts that the language represents is (presumably) Turing-complete.

As to information theory, what are the 'words' in the language and what is the syntax for well-formed words?

Improve this answer
4
  • 1
    I think that you are essentially restating my que
    – Roger V.
    Mar 6, 2020 at 21:20
  • What is obvious from this answer is that the computer science and the linguistics define language differently: computer language is equivalent to "syntax" of human language (plus a few auxiliary words.) Once we account for this difference, your answer essentially confirms what I said: to make a computer language us equivalent to a natural one, if you add the lexicon - the things to compute.
    – Roger V.
    Mar 6, 2020 at 21:24
  • Sorry for typos - deficiency of SE smartphone application. There is also a pragmatic aspect: computer language does not serve communication.
    – Roger V.
    Mar 6, 2020 at 21:27
  • @Vadim An important point was mentioned — adding additional rules (e.g. for type checking or agreement) can make a CFG formally stronger (CSG or even more powerful). The bad news is this makes parsing NP-hard.
    – Atamiri
    Mar 6, 2020 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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