9

What is a 'context-free grammar' in relation to natural languages? This Wikipedia article, gives a broad description, but it isn't clear exactly what features of a language would result in it not being considered context free, or being considered so.

What is the fundamental property of a grammar that would result in it being context-free or non-context-free? Why is this property of special interest to linguists?

Ideally an answer would be digestible by readers with no mathematical background.

Sir Cornflakes
  • 30,154
  • 3
  • 65
  • 128
Araucaria - him
  • 4,002
  • 1
  • 15
  • 39
  • Linguists use different types of tools to describe the grammars of languages. Some linguists use formal languages for description, and CFGs are one of the tools from formal language theory that have been explored. Most linguists find CFGs too clumsy and restrictive to use, and thus most have not been using them, but there are some, like @Greg Lee, who still do. – WavesWashSands Feb 16 '18 at 15:08
  • Fundamentally, since a CFG consists of a finite set of CF rules, if a grammar has an infinite number of rules, or any rules that are not CF, then it fails to be a CFG. Since we can't observe grammars directly, it's a tricky question to try to answer. – Greg Lee Feb 16 '18 at 19:24
  • A better way to put the question, as I understand the intent, is, "What attested property of natural language putatively cannot be generated by a CFG, according to a certain proof by Chomsky (or Postal)". You can tell by inspection if a grammar is a CFG: you cannot tell by inspection if you're looking at the language = set of strings. – user6726 Feb 16 '18 at 20:53
  • @user6726, Yes, but you can't actually tell by looking at the set of strings making up the language, either. You'll only have time to examine a finite number of them, and every finite set of finitely long strings can trivially be generated by a CFG. Just list them. – Greg Lee Feb 16 '18 at 23:57
  • Hence my contrast between grammars and languages. – user6726 Feb 18 '18 at 05:58
  • @GregLee A grammar with an infinite number of rules can still be equivalent to a CF grammar, in fact this happens a lot in formalisms such as LFG where the right-hand side of a rule can be a regular expression, that is, a schema representing a countable number or rules. – Atamiri Feb 20 '18 at 11:09
  • I would say Chomsky's research helped computer science a lot, especially in terms of parser, compiler etc. Its help and insight on human languages? Not a lot really. He is a brilliant political commentator and activist, but many of his linguistic ideas are just ridiculous. – xji Feb 24 '18 at 15:04

3 Answers3

4

Sometimes technical descriptions are made with technical vocabulary neologisms in order to capture complicated and nuanced concepts which might be ungainly to convey correctly with simpler non-technical terms. So it may be difficult to come up with a description of a technical concept using only non-technical terms.

A rule in a language is context-free if the rule (affecting some words together) does not use text surrounding those words in order to apply correctly.

For example, suppose you want to make a comparative out of an adjective. Just add '-er': hot -> hotter, tall -> taller. For longer words, you use 'more' first: 'more consistent', 'more independent'. And then for a few words, like 'good' you have a rule exception: 'better'. For all of these, it doesn't matter what the word is, you don't need to know anything else in the sentence to form that comparative: in 'he is good' and 'he is better', the comparative doesn't depend on anything else in that sentence outside of what happens to the adjective.

In contrast, one might say that conjugation of verbs is context-sensitive (the alternative to context-free). For example, in the present simple in English, it is 'I say' and 'he says': to get the right ending on the verb, you need to know the context (the pronoun that comes before). The pronoun itself is not part of the thing that changed, but its presence changed the following word.

Mitch
  • 4,455
  • 24
  • 44
  • 1
    Araucaria, I hope this is in the direction of what you want. It is non-mathematical. It is written for a (very?) non-technical audience. If you are really seeking a technical definition, but one that is not mathematical but applies to natural language, I'm not sure if that needle can be threaded because technical (or stipulated) vocabulary is practically mathematical in its use. – Mitch Feb 16 '18 at 16:41
  • What does the parenthetical "affecting some words together" mean / do? Does that mean that a context-free rule can simultaneously apply to two words? Do such grammars only operate on whole words? – user6726 Feb 16 '18 at 16:46
  • No, conjugation of verbs isn’t context-sensitive. Agreement is an orthogonal mechanism. A toy grammar accounting for agreement would still be context-free. – Atamiri Feb 16 '18 at 16:58
  • @user6726 All grammars operate on whole words. “Context-free” refers to rules being applied piecewise, possibly in parallel or in any order, without looking at the surrounding context. – Atamiri Feb 16 '18 at 17:01
  • So the concept of context-free is undefined for morphology and phonology? – user6726 Feb 16 '18 at 17:45
  • @user6726 It only makes sense for phrase structure rules. I’ve seen “sublexical” grammars so it’s possible for morphology and even makes sense for agglutination. – Atamiri Feb 16 '18 at 17:50
  • Provided the number of different agreement classes is finite, such things as verb agreement remain context free. One can simply add a few non-terminal symbols for the various agreement classes. CFG limits the number of such classes to being finite, but small finite numbers are not a problem. In fact, it is reasonable to claim that the fact that the number of agreement classes in a human language is always small (and surely not unbounded) substantiates CFG theory. – Greg Lee Feb 16 '18 at 18:07
  • @user6726, No, CFG is still defined for phonology and morphology. CFG allows for large subclassifications,provided only that they remain finite in number. Say, for instance, that the number of phonemes is always finite, though the number of phones is unbounded. A morphophonemic rule of assimilation of contiguous phonemes would be CF, but not a phonological rule assimilating contiguous phones, because the latter would require an unbounded number of cases to describe. CFG can have only a finite number of rules. (cont. ...) – Greg Lee Feb 16 '18 at 18:36
  • (... cont) Stephen Anderson once proposed that different continuous amounts of aspiration are produced by different amounts of stress on the following vowel, and this shows that phonology is not CF. – Greg Lee Feb 16 '18 at 18:39
  • It is indeed in the direction I was after (clear, digestible). However, I'm a bit confused about the agreement thing, mainly because other comment here seem to contradict your agreement example. Perhaps you could provide an alternative (I'm aware of the "one might say" hedge that you carefully included your answer!). – Araucaria - him Feb 19 '18 at 14:50
  • @Araucaria yes, the hedge was intentional. Sure, there's the technical ideas of the difference between a grammar and a language (a grammar may be context sensitive, but the language it describes may be inherently context-free. I think those who say morphological agreement is context free are saying that one is able to create a CFL for it, even though it may not be the first one you think of). But if you are interested in getting across the idea of context-free-ness to a non-technical audience it might be sufficient. – Mitch Feb 19 '18 at 15:12
  • @Araucaria In English syntax, maybe the rule for who vs what ('who' for sentients)? Any syntax rule that is non-adjacent might be more easily constructed context sensitively though with some cleverness a context-free version might be made. If you want to stick with syntax, maybe the classic transformations like 'He gave it to me' -> 'He gave me it' (I'm not thinking deeply about how or why either of those might be CF or CS, just that their is a parse tree transform)? Phonology has lots of context sensitive like things but might get too techy with the diff between spelling and IPA. – Mitch Feb 19 '18 at 15:17
  • @Araucaria As for agreement, a rule for that only combines the head with its dependent, agreeing or not, there’s no context taken into account. In CFG, a “context” is another symbol to the left or right of the left-hand side of the rule, something like αXβ, which is clearly not the case here. In general, context-sensitivity in formal grammars is often hidden in constraints that rule out some phrase structures making the resulting language stronger formally. In the case of agreement the language remains CF. – Atamiri Feb 20 '18 at 09:01
  • @Atamiri I'm pretty sure that Araucaria is well versed in the formal aspects of CFGs and CSGs with respect to formal grammars and natural languages. I think what he is looking for is an informal introduction to the concepts to show why it is even an issue at all. – Mitch Feb 20 '18 at 14:15
  • @Araucaria As you well know, a desired property of language that makes it non-regular and necessarily context-free or above is unlimited nesting: 'the man that caught the dog that chased the cat that found the rat that ate the cheese...'. I think you're looking for a desired property of natural language that would require context-sensitive rules (and this property should be understandable informally, without a lot of mathematical baggage). – Mitch Feb 20 '18 at 14:22
  • 1
    @Araucaria From poor memory, I feel like Syntactic Structures has examples (possibly too formal) where context-sensitive transformations are used (i.e. I think Chomsky was saying that CFGs were not enough and made a good case for it here). What those language properties were I can't remember. Agreement was one thing mostly ignored there, but it is the only thing that feels context sensitive to me. How about pronoun matching across subtrees? Any property where information in one subtree needs to be known about in another parse subtree (in the same sentence)? – Mitch Feb 20 '18 at 14:36
  • @Mitch That sounds like a good way to go. Thanks. – Araucaria - him Feb 20 '18 at 15:01
1

There are no fundamental properties. Some/most (?) natural languages are mildly context-sensitive to allow for features such as cross-serial dependencies. Pure context-free grammars are too cumbersome to be used in linguistics, one needs to add a constraint system (in the form of a formal logic, typical an equational logic) which makes the whole system Turing-complete even if the backbone is a context-free grammar.

Atamiri
  • 2,590
  • 1
  • 14
  • 15
  • Thanks for the answer, but you haven't explained what a context-free grammar actually is, yet. – Araucaria - him Feb 16 '18 at 11:31
  • @Araucaria The definition can be found in the Wikipedia article. Think of it as a system that piecewise generates sequences of symbols (piecewise=not taking surrounding context into account). – Atamiri Feb 16 '18 at 13:12
1

CFG (context free phrase structure grammar) is important in linguistics, even fundamental, because it is what allows us to describe natural language expressions with hierarchical tree structures, which have become the universal descriptive tool of grammarians. Many linguistic theories are variants of CFG; e.g., Reed-Kellogg diagramming, tagmemics, the base component of transformational grammar, GPSG (Generalized Phrase Structure Grammar), dependency grammar.

Among the grammatical constructions in human languages which seemingly cannot be properly described by a CFG are cross serial dependencies, mentioned by Atamin above, and various constructions with discontinuous constituents, such as RNR constructions (in McCawley's theory of them).

I am an enthusiast for CFG, personally, though the consensus of contemporary syntacticians is that CFG is not sufficient to describe human languages.

Greg Lee
  • 12,466
  • 1
  • 18
  • 32
  • Dependency grammar? Not true in general. – Atamiri Feb 16 '18 at 17:02
  • Discontinuity doesn’t necessarily entail context-sensitivity. – Atamiri Feb 16 '18 at 17:05
  • @Atamiri, I think it is true that DG is a kind of CFG, in the sense that every longuage generated by a DG can be generated by some CFG. I've found a reference by Stephen Abney here, http://www.vinartus.net/spa/94g.pdf which questions a proof by Gaifman,which proof I take to support my view. I don't follow all the details, but Abney seems to be talking about whether CFGs always generate headed constructions. I don't see the relevance, especially since human languages do have headless constructions. – Greg Lee Feb 17 '18 at 18:20
  • There are DGs that are stronger than CFG but DG isn't a precisely defined term so there's definitely a subset of DGs which is equivalent to CFG. I'll look at the reference you provided. – Atamiri Feb 17 '18 at 20:53