5

I've read that a context-free grammar is one in which every production rule is written in the way V -> a, where V is a non-terminal symbol and a is a chain of non-terminal and terminal symbols.

In English we have non-terminal symbols like Verb, Adjective, etc.

But in a sentence, almost all verbs have an extra -s,if the subject is in the third person singular.

How could this be accounted for by a context-free grammar?

If English grammar was context-free, it would have production rules like Verb -> sing, or Verb -> sings - but how could we correctly pick up sing or sings in a context-free grammar, if the left-hand side of the production rule must be a single non-terminal symbol, and hence cannot contain the subject of the sentence (at least not always)?

In other words, how can the word “sing” be properly transformed, when such a rule could not take into account other words in the context, like who the subject of the verb is?

Improve this question
5
  • 1
    Hypothesis: if all we want is a parser we can get a parser that produces a correct parse tree from valid sentences by ignoring noun-verb agreement.
    – Joshua
    Commented Jun 11, 2023 at 19:25
  • 1
    People underestimate the power of finite but unlimited assets. Congruence is an obvious problem for CFG, and pseudo-parametrisation by multiplying out states is a (to computer scientists) obvious solution. The required number of states makes it totally impractical, but C.S. theory doesn't care about practical limits on something as long as it's not actually infinite.
    – Kilian Foth
    Commented Jun 12, 2023 at 14:22
  • @KilianFoth your comment sounds rich with insight, but is above my head for its technicality - I would really appreciate if you could elaborate, as I’m intrigued to know more, and I think the question could also benefit from it.
    – Julius Hamilton
    Commented Jun 26, 2023 at 6:17
  • @KilianFoth If people recognise the existence of anything '…finite but unlimited…' can you say why Google doesn't recognise that wording?
    – Robbie Goodwin
    Commented Jun 28, 2023 at 18:33
  • Is anyone suggesting the only meaningful part of the Question is whether natural grammars 'cannot' be context-free? Conversely, are people denying that they could be, please?
    – Robbie Goodwin
    Commented Jun 28, 2023 at 18:57

2 Answers 2

Reset to default
11

Imagine a very simple CFG that only handles nouns and verbs.

S → N V
N → dogs | cats | Alice | Bob
V → walk | play | eat

Right now this can't handle agreement. But it can with a small change:

S → Nsing V s
S → Npl V
Nsing → Alice | Bob
Npl → dogs | cats
V → walk | play | eat

Just add more categories! Now it correctly produces Alice walks but cats walk.

This is not a great solution. It gets unwieldy very quickly when you have more forms of agreement to deal with. But it works well enough, in general, that it's not obvious that it can't work in every case.

Improve this answer
9
  • 1
    Thank you! right, of course, it was stupid to assume that the context-free production rule cannot contain the subject and the predicate in the right-hand side.
    – Qwertuy
    Commented Jun 10, 2023 at 19:44
  • This helps me understand “context-free” in a simple way I had not, before. Context-free literally means “unary operator” in math. You can map an element to another but the mapping does not take more than one argument. A function f(x, y) is “context-dependent” because it is the same as an if-conditional: if x=3, then f(x, y)=7. A grammar that chooses the replacement for an incoming sequence depending on the presence of a nother symbol is exemplifying an “if”-clause. It took me a while to see how simple that is. I like the term “transcription machine” - the simplest level of “translation”.
    – Julius Hamilton
    Commented Jun 11, 2023 at 8:25
  • 1
    More likely specify categories Vsing and Vpl, rather than hard-coding the suffix.
    – Barmar
    Commented Jun 11, 2023 at 13:10
  • 1
    @hmltn That is not a bad way to see it, however keep in mind that thanks to the technique of "currying", formally there is no need to ever need more than one argument. E.g. you can first apply the argument 3 to generate the partial function f(3,.) and then evaluate that at y and so on. In fact that is precisely what happens in this answer. The only caveat that prevents this from always working in the context of grammars is that there is only a finite number of symbols allowed, which in this case translates to finitely many different possibilities of f(x,.).
    – mlk
    Commented Jun 12, 2023 at 7:05
  • Thank you. Let me see if I understand that totally (out of a desire to learn more). What you describe as “currying” to me sounds like it requires a concept of “partial function” - an object that is a function with two arguments, but only one of them (yet) selected. But that still qualifies as a function which is defined in terms of 2 arguments, right? A formal system which truly has no concept of binary mappings, not even partial ones, could never emulate the characteristics of a conditional (I think). You either have f(x) = a, a 0-level type (terminal, non-predicative, a set element or number
    – Julius Hamilton
    Commented Jun 12, 2023 at 10:00
4
  1. Nothing in mathematics is ever obvious until after it is proven.

1.1 This is one reason English not being a CFG is not "obvious".

  1. A right-linear grammar can generate English, because a right-linear grammar over some alphabet, can generate all possible strings of that alphabet.

2.1 A right-linear grammar can generate all of the strings of English - it can actually generate more sentences than just the sentences of English. You can't just be concerned with whether a grammar of a certain type can generate a certain class of strings. The question has to be more specifically about exact generation. Can grammar G generate a certain class of strings, and not generate other stuff? Is it possible to generate English and only English, with some right-linear grammar? Or, can a suggested grammar also generate Mohawk? Or generate some other language? The supposed grammar does not succeed, when it over-generates - when it generates more strings, or sentences, than are considered allowable or correct, in the language.

2.2 The correctness of a formal grammar, or a theory of grammar, is that it generates exactly the sentences of a language L - no more, and no less.

  1. There is a reasonably easy-to-come-up-with solution to the grammatical feature you mentioned regarding noun-verb agreement for number (which @Draconis provides). But does this type of solution generalize to all human languages?

3.1 Shieber 1985 provides evidence against that context-freeness claim. Their argument comes from Swiss German data. And there is a similar argument proffered in [Culy 1985]. Their argument is based on data from Bambara.

  1. You can easily tell from inspection of a grammar whether it is context-free or context-sensitive.

4.1 But the reverse is not true: you cannot easily tell from inspection of a set of strings, whether or not that exact set can or cannot be generated by a context-free grammar. We don't really fully yet understand what kinds of languages can and cannot be generated by C.S. vs. C.F. grammars. At least when explained in ordinary linguistic terms.

4.2 We don't really know what kind of facts could constitute an "impossible language" for CF grammar. Though Culy and Shieber have given us some suggestions. In short, none of this is "obvious".

Improve this answer
1
  • I'll try to respectfully do some minor edits on this answer, if it'd be alright, because it's a very good answer, I'd just like to try to expand each of the points you made. Of course, feel free to revert if you don't like the edits, I would welcome that. Thank you.
    – Julius Hamilton
    Commented Jun 26, 2023 at 6:50

Your Answer

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

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