Shieber (1985) @cite{shieber-1985} #

Evidence against the Context-Freeness of Natural Language. Linguistics and Philosophy, 8(3), 333–343.

Core Argument #

@cite{shieber-1985} proves that Swiss German is not weakly context-free, using a purely string-based argument that makes no assumptions about constituent structure or semantics. The proof rests on four empirical claims about Swiss German subordinate clauses, plus the closure of context-free languages under string homomorphism and intersection with regular languages (proven in Linglib.Core.Computability.ContextFreeGrammar.{Map, InterRegular} following @cite{bar-hillel-perles-shamir-1961} / @cite{hopcroft-motwani-ullman-2000} Theorems 7.24, 7.27).

The Four Claims #

Swiss German subordinate clauses have structures where all Vs follow all NPs.
Among such sentences, those with all DAT-NPs before all ACC-NPs, and all DAT-Vs before all ACC-Vs, exist as a regular-intersection-filterable subset. This is not a grammaticality condition on Swiss German itself — SG freely allows interleaved NP orderings — but the case-sorted subset is what Shieber's homomorphism + regular intersection isolates.
The number of DAT-Vs equals the number of DAT-NPs (and similarly for ACC).
An arbitrary number of Vs can occur (subject to performance).

What Is Formalized Here #

swiss_german_not_contextFree proves: Swiss German subordinate clauses are not weakly context-free. The language swissGermanLang allows any token sequence whose cross-serial core (after stripping matrix boundary tokens — matrix subjects, complementizers, auxiliaries, finite verbs of the embedding clause) has shape nps ++ vs with case counts matched. Matrix tokens may appear interleaved anywhere; Shieber's homomorphism erases them.

The proof exercises both legs of the Bar-Hillel schema (Language.not_isContextFree_via_witness from Closure.lean):

Homomorphism leg (tokenStringHom): cross-serial NPs and Vs map to singleton {a,b,c,d} letters; matrix tokens map to [] (Shieber's ε-erasure).
Regular-intersection leg (caseSorted = a*b*c*d*): selects only case-sorted images, isolating the canonical cross-serial shape from any source-string interleaving of cross-serial tokens.

The witness language stringMap h L ⊓ R = ambncmdn — non-CF by ambncmdn_not_contextFree (two-parameter pumping). Per the Bar-Hillel schema, source SG is non-CF.

Proof bottoms out at the two CFL closure theorems in Linglib.Core.Computability.ContextFreeGrammar.{Map, InterRegular} (homomorphism + intersection-with-regular, both proven; see those files for @cite{bar-hillel-perles-shamir-1961} / @cite{hopcroft-motwani-ullman-2000} construction details) and ambncmdn_not_contextFree (the two-parameter pumping result) in Linglib.Core.Computability.NonContextFree.

A weaker pedagogical waypoint, swiss_german_diagonal_not_contextFree, uses only the simpler one-parameter anbncndn substrate; it covers just the diagonal (m = n) subset of SG clauses with no matrix material.

Remaining idealizations #

The matrix token is a single abstract constructor, not a richer model of SG matrix material's internal structure (specific lexical items, agreement, finite-verb fronting). For Shieber's purpose — showing non-CFness of the string set — this abstraction is faithful: he too treats matrix material as an erasable substring under the homomorphism. A richer model that ties matrix-token positions to specific SG fragment data would be a substantive extension; the current formalization captures Shieber's full argument without it.

Contrast with @cite{bresnan-etal-1982} #

@cite{bresnan-etal-1982}'s earlier argument for Dutch non-context-freeness relied on linguistic assumptions about constituent structure, which @cite{gazdar-pullum-1982} contested. @cite{shieber-1985}'s argument is purely formal — it rests entirely on the string set of Swiss German and the case-marking facts, making no claims about phrase structure.

Subsequent literature #

@cite{huybregts-1976} gave a contemporaneous Swiss German argument.
Joshi (1985) introduced TAG and the mild-CS hierarchy; Vijay-Shanker–Weir (1994) established the equivalence of TAG/CCG/MCFG/MG within mild-CS. The MCS classification of cross-serial dependencies is post-Shieber and not attributable to him; he proved only not weakly CF.
Manaster-Ramer (1987) raised concerns about the universality of Shieber's case-matching premise.
Stabler (1997) and Kobele (2006) provide MG analyses of the same data.

The processing-side dissociation (cross-serial easier than nested despite greater formal complexity) is the subject of @cite{bach-brown-marslen-wilson-1986}, formalized in Phenomena.WordOrder.Studies.BachBrownMarslenWilson1986 — not duplicated here.