6

I have a decent understanding of regular languages, CFLs and r.e. sets from a course in computer science theory. I'm just learning about the Chomsky hierarchy.

As an English speaker, I have a somewhat intuitive sense of why natural language is not regular. For instance, you could have sentences such as "the cat ran" => "the cat [who lived in London] ran" => "the cat [who lived in London [but traveled to France]] ran" ... each time you recursively expand the string, a subject just agree with an object. In general, you need something more powerful than a regular language to capture strings like {w | 0^n,1^n }. Thus, intuitively, it makes sense that you'd need something like a CFL to generate potentially infinite strings.

But why do linguists think CFL are insufficient? Related: does anyone thing that natural language is actually r.e?

Improve this question
2

2 Answers 2

Reset to default
10

I don't personally believe that CFL are insufficient, but among linguists who care about weak generative capacity (probably most don't care about the issue), the consensus seems to be that they are. The usual reference given is an article by Peter Shieber, which is online here, and which is, in my opinion, an admirable work of scholarship. (Which doesn't make it right, of course.)

So far as I know, the case rests on the grammaticality of unbounded cross-serial dependencies in certain natural languages, see Cross-serial dependencies. Or, one might refer to them as "respectively constructions".

A conceptual example would be "John smoked, ate, and drank cigars, caviar, and brandy, respectively", supposing that is interpreted as meaning "John smoked cigars, John ate caviar, and John drank brandy". The problem is getting the verbs to pair up with the objects that they go with. What seems to be a corresponding problem with CFL is generating "copy" languages, which have sentences with two consecutive copies of the same string, which is provably impossible in general.

So far (you're probably thinking) this seems to be an imaginary problem, since the English example I gave above is not actually grammatical. If by proposing CFL for natural languages, we predict that natural languages cannot have such constructions, that would seem to be a good thing.

The problem is that some other languages do seem to have such constructions. Shieber described a Swiss-German dialect, and others have since been found. So even if it happens that English doesn't have cross-serial constructions, since we're interested in human language in general, we have to give up on CFL as a general model.

I don't, myself, think this argument has any force, since the only real prediction that CFL makes is that the depth of cross-serial constructions must be bounded and that the greater the depth of the cross-serial construction the more complex the CFL must be to emulate it. That is the situation in Swiss-German, in Shieber's account. Two-depth CS constructions are accepted by all, three-depth ones by some, but four-depth ones are not accepted by anyone. So, in my view, the facts actually support the theory that natural languages are context free, rather than showing that they are not.

On your last question, yes, quite a few people believe that natural language is r.e., recursively enumerable, i.e., since all the languages in the Chomsky hierarchy are r.e. One of the dissidents, I believe, would be C. F. Hockett, who proposed in The State of the Art, reviewed here by Chuck Fillmore, that human languages do not have definite systems of the sort that Chomsky assumes.

Improve this answer
1

One example is generating relative clauses parses with an intuitive structure. In a CFG, we'd need to define new rules to deal with the syntax of the relative clause in the following sentence, since "saw", a transitive verb, isn't taking an object in the expected position (this would give us a grammar that has the same weak generative capacity as what we desire, but not the same strong generative capacity).

The boy that I saw cried.

We could get around this by defining a whole new set of rules for each subcategorization verb type when it appears inside a relative clause, but this gets messy. On the other hand, a mildly context sensitive formalism like CCG lets us produce the desired parse without having to define any new syntactic categories. In the following derivation, we achieve this with type-raising going from line 1 to 2:

the : boy : that : I : saw : cried

NP / N : N : (NP \ NP) / (S / NP) : NP : (S \ NP) / NP : S \ NP (1)

NP / N : N : (NP \ NP) / (S / NP) : S / NP : S \ NP (2)

NP / N : N : (NP \ NP) : S \ NP

NP : (NP \ NP) : S \ NP

NP : S \ NP

S.

It's worth noting that recovering the semantics for such sentences from a parse becomes much simpler once we move up to CCG.

Improve this answer
2
  • No, the method of slash categories doesn't "get messy" with relative clauses; on the contrary, Gazdar shows that both Ross's Coordinate Structure Constraint and his across-the-board condition are predicted. Defining a finite number of "new" categories is not a problem in CFG, since since the theory requires merely that non-terminal symbols and rules be finite.
    – Greg Lee
    Commented Apr 20, 2017 at 21:46
  • Yes, of course it's possible to write a CFG that accepts relative clauses because the set of categories is still finite, but we can't get the same semantically motivated parse structure that we can achieve with CCGs (weak generative capacity versus strong generative capacity).
    – William Merrill
    Commented Apr 20, 2017 at 21:59

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.