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.
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:
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.
