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.

7
  • 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. 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 5:58
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.

17
  • 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
  • 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
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.

2
  • Thanks for the answer, but you haven't explained what a context-free grammar actually is, yet. 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.

4
  • 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, 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

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.