7

Could anyone give examples of context-sensitive sentences that cannot be generated by context-free rules?

To clarify, they are generated by rules including at least one that is in the form αβγ→αψγ, α,γ are not empty and we cannot find any context-free grammar that can generate it.

EDIT "Language" here means natural languages.

  • Any reason for your downvotting?Please tell me :) – XL _At_Here_There Aug 28 '13 at 22:56
  • Not personally responsible for the downvote, but i suspect it's because it looks like you tried to insert some symbols and they haven't came out right. The question itself is interesting and on topic, i think. – P Elliott Aug 28 '13 at 23:06
  • @PElliott,thank you,the website can not parse latex,so the production rules has not displayed as we usually expect.The website is not like matheoverflow or stackcs ,strange. – XL _At_Here_There Aug 28 '13 at 23:14
  • 1
    I've also noted that we can't use LaTeX commands here and I do sometimes miss this feature. I'm going to open a discussion on meta about this. – robert Aug 28 '13 at 23:50
  • @XL_at_China Also, when you say "Could anyone give examples of context-sensitive sentences that cannot be generated by context-free rules?", do you mean sentences generated by context-sensitive rules? – P Elliott Aug 29 '13 at 0:17
4

The most famous example of a phenomenon which seems to argue against the context-freeness of natural language is cross-serial dependencies in Swiss German (Schieber, '85) (cross-serial dependencies can also be found in Dutch).

Two facts about Swiss German are relevant here:

  1. Objects are case-marked (dative and accusative), diff. verbs sub-categorise for objects with different case-marking.
  2. Subordinate clauses allow a cross-serial order.

Here's the pertinent data. I'll just give the English gloss, see the linked-to paper for details:

(a) ...Jan said that we Hans.DAT1 [the house].ACC2 helped1 paint2

Note the cross-serial dependencies; Hans is the object of helped, and the house is the object of paint.

Now onto the proof that a context-free grammar can't handle cross-serial dependencies. This is going to be fairly sloppy, but bear in mind that this is an established result in the literature.

We're going to give a proof by contradiction, so let's assume that the L (Swiss German) is context free. Therefore the intersection of a regular language with the image of L under a homomorphism must be context free as well. Now consider the following grammatical Swiss German example:

(b) Jan said that we [the children].ACC1 Hans.DAT2 house.ACC have wanted let1 help2 paint

The < NP, V > pairs < the children, let > and < Hans, help > can both be iterated.

The following homomorphism f seperates the iterated NPs and Vs in (b) from the surrounding material:

f(the children) = a
f(Hans) = b
f(let) = c
f(help) = d
f(Jan said that we) = w
f(house have wanted) = x
f(painted) = y
f(s) = z otherwise

The images we are interested in under f are of the form wV1xV2y, where V1 contains as and bs, and V2 contains cs and ds, and if the kth element in V1 is an a (a b resp.), then the kth element in V2 is a c (a d resp.) - i.e., sentences involving cross-serial dependencies. All other sentences have a z somewhere in their image under f. To make sure we only concentrate on constructions involving cross-serial dependencies, we intersect f(L) with the reg. language wa*b*xc*d*y, giving us L'.

If L is context free, then L' must be too. If this is so, then the image of L' under a homomorphism f' with f(w)=f'(x)=f'(y)= Ɛ, f'(a)=a, f'(b)=b, f'(c)=c, f'(d)=d will also be context free. This image is:

f'(L') = L'' = { a^i b^j c^i d^j | i, j >= 0 }

L'' should satisfy the pumping lemma for context free languages. Inspecting the word {a^k b^k c^k d^k}, where k is the constant from the pumping lemma however, this can be shown to lead to a contradiction.

In conclusion L'' is not context free, and neither is L' nor L. The take-home message is that purely context-free grammars cannot handle cross-serial dependencies in natural languages - although examples of this are few and far between. This result has been used to argue that natural languages are properly described by mildly context-sensitive languages.

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.