Three Models for the Description of Language

(1) Finite-state Markov processes producing sentences left to right, (2) phrase-structure grammars, (3) transformational grammars built on top of phrase structure.

No finite-state Markov process can serve as a grammar of English, and n-th order statistical approximations don’t approach English as n grows. Phrase structure is essentially more powerful but succeeds only for a small set of simple sentences. English grammar is much simpler with phrase structure limited to a kernel of simple sentences from which all others are derived by transformations.

Like a theory based on finite observations that projects them by general laws to predict new phenomena: a grammar is based on a finite corpus and projects it to an infinite set of grammatical sentences by rules framed in terms of constructs (phonemes, words, phrases).

How to choose a grammar for each language from a finite corpus; equivalently, the ability of a speaker to produce and understand new sentences, and to reject other new sequences as ungrammatical, on the basis of limited experience.

A device that produces all of the strings that are sentences of L, and only these. A language is a (finite or infinite) set of finite sentences over a finite alphabet.

A grammar built for a corpus containing neither should project it to include the first and exclude the second. For one language this is a weak test, but for a general theory it is strong, since every language’s clear cases must be handled in a fixed, predetermined manner.

(3) Are there interesting languages (like English) simply outside its range of description? (4) Can it give reasonably simple grammars for all interesting languages? (5) Are those grammars “revealing”: does the structure they assign support semantic analysis and give insight into the use and understanding of language?

Grammars must be finite, so any theory makes only countably many grammars available, while there are uncountably many languages (sets of strings).

It starts in an initial state, runs through a sequence of connected states and ends in the initial state again, producing one of the transition symbols at each step; the strings so produced form a finite-state language.

Sentence \(S = a_1 \ldots a_n\) has an \((i, j)\)-dependency if replacing the \(i\)th symbol by some \(b_i\) makes a non-sentence, and then also replacing the \(j\)th symbol by some \(b_j\) makes it a sentence again: the choice at \(i\) constrains the choice at \(j\).

A dependency set (non-overlapping, nested dependencies) with \(m\) terms requires at least \(2^m\) states, so for a finite-state language there is a bound \(m\) such that no sentence has a dependency set of more than \(m\) terms.

Over {a, b}: \(L_1\) = \(a^n b^n\) (n a’s then n b’s: ab, aabb, …); \(L_2\) = mirror-image strings \(X\) followed by \(X\) reversed (aa, bb, abba, …); \(L_3\) = \(X\) followed by \(X\) itself (aa, abab, …). Each has sentences with arbitrarily many nested or crossing dependencies.

Constructions like “If S1, then S2”, “Either S3, or S4” and “The man who said that S5, is arriving today” have dependencies (if–then, either–or, man–is) around clauses that can themselves be such constructions, giving English subparts with the mirror-image properties of \(L_1\) and \(L_2\).

It serves no useful purpose: there are sentence-forming processes the model is intrinsically incapable of handling. With a limit a finite-state grammar exists (a list is one), but it would be too complex to be of use or interest.

A finite-state process with a state per sequence of \(n\) words, emitting each next word with its conditional probability given those \(n\) words. As \(n\) grows the output looks more and more like English.

It is grammatical (read with normal sentence intonation), while “furiously sleep ideas green colorless” is not (read with falling intonation on each word), yet plausibly no pair of their words ever occurred together. No order of approximation distinguishes them: there is no general relation between frequency and grammaticalness.

An \(n\)th-order approximation excludes, as improbable, an ever-increasing number of grammatical sentences while still containing vast numbers of ungrammatical strings; ordering strings by approximation scatters grammatical and ungrammatical ones throughout.

No: each \(n\)-order approximation is a finite-state process, but not conversely. A three-state process (one loop of b’s bracketed by a…a, another by c…c) yields dependencies of any length that no fixed \(n\) captures.

Grouping the words of a sentence into phrases, these into smaller constituent phrases, and so on down to the ultimate constituents (generally morphemes), with phrases classified as NP, VP, etc.

A complex class of expressions like NP is stated once in the grammar and then used as a building block at various points in sentences.

A finite vocabulary \(V_P\), a finite set \(\Sigma\) of initial strings and a finite set \(F\) of rules \(X \to Y\) (“rewrite X as Y”), where Y is formed from X by replacing a single symbol with a string. A derivation is like a proof, with \(\Sigma\) as axioms and \(F\) as rules of inference.

Σ: # Sentence #. F: Sentence → NP VP; VP → Verb NP; NP → the man, the book; Verb → took.

Equivalent derivations differ only in the order in which rules are applied and reduce to the same diagram. A substring is an X if it traces back to a single node labelled X: “the man” is an NP, but “man took” is not a phrase at all.

A sentence receiving nonequivalent derivations from the simplest grammar. Rules for “they are flying – a plane” and “(flying) planes – are – noisy” give two structures: they – are – [flying planes] (those specks are flying planes) and they – [are flying] – planes (those pilots are flying planes). The formal ambiguity explains the semantic one.

Check whether cases of constructional homonymity are actually cases of semantic ambiguity: a revealing grammar gives ambiguous sentences alternative analyses.

Context-sensitive rules (rewrite X as Y only in the context Z–W), and ordering the rules in a sequence with obligatory and optional rules; these simplify the grammar without changing its generative power.

Every finite-state language is a terminal language (generated by a phrase-structure grammar), but not conversely; every derivable language is terminal, but not conversely; some derivable languages aren’t finite-state and some finite-state languages aren’t derivable.

Phrase-structure description is essentially more powerful, not just simpler, than finite-state grammars producing sentences left to right. \(a^n b^n\) is a terminal language (Z → a b, Z → a Z b), so the mirror-image argument against finite-state models doesn’t apply to phrase structure.

Its description uses symbols that aren’t in the language’s vocabulary (\(V_P\) properly includes \(V_T\)): Sentence, NP, VP are not words of English.

Its state is determined by which initial strings occur in the last string produced, and it moves on by applying a rule to that string: at each point the process depends on its present state and a bounded amount of the last output.

No: he didn’t know whether English is a terminal language (\(L_3\), copies \(XX\), is not), so he couldn’t disqualify phrase structure on that ground. He rejects it on the complexity of description.

Verb → Auxiliary V; Auxiliary → C (M) (have en) (be ing), with M a modal and C past or present: one obligatory element and optional ones in fixed order. Discontinuous pieces (have…en, be…ing) then combine freely.

The rule Af v → v Af # (moving each affix after the following verb-like element) uses discontinuous elements and must know that e.g. “take” is a V: it needs the constituent structure (the derivation history) of the string, not just the string itself.

It doesn’t combine freely: it can’t occur with intransitive verbs (“John has been come”), is excluded in the context “the man — the food” and required in “the food — by the man”. Removing it and adding a passive rule makes all these restrictions automatic.

If NP1 – Auxiliary – V – NP2 is a sentence, so is NP2 – Auxiliary + be + en – V – by + NP1: “the man – past – eat – the food” gives “the food – past be en – eat – by the man” → “the food was eaten by the man”.

A rule that converts every sentence with a given constituent structure into a new sentence with derived constituent structure, related in a fixed way to the original. Rules like affix hopping and the passive are transformations, beyond phrase structure.

By a restricting class R (the sequences \(X_1, \ldots, X_r\) a string with its phrase marker must be analysable into, e.g. NP, Auxiliary, V, NP for the passive) and an elementary transformation \(t\) (the structural change made to the analysed parts).

The set of strings occurring as lines in a maximal set of equivalent derivations of a sentence; a string has more than one phrase marker iff it has nonequivalent derivations.

Phrase-structure rules produce a terminal string; transformations give morphemes in the correct order; morphophonemic rules (have + past → had, take + ing → taking) give phonemes.

Obligatory ones (like affix hopping) must apply or the result isn’t grammatical; optional ones (like the passive) may or may not. Kernel sentences are derived from phrase-structure strings by obligatory transformations only; all others come from optional transformations.

The grammar is greatly simplified if the kernel is a very small set of simple, active, declarative sentences (probably finite), with questions, passives, conjunctions and complex noun phrases derived by transformations, which can compound (e.g. questions from passives).

Transformations are by and large meaning-preserving, so the kernel sentences underlying a sentence can be seen as the elementary content elements in terms of which the actual (usually complicated) transform is understood.

Each transformation is finitely characterizable, and its restricting class bounds how much information about a string (how much derivation history) is needed to apply it; more than the last line must be inspected, but still a bounded amount.

The simplest phrase-structure grammar gives “they are flying planes” two derivations, matching its ambiguity; there’s no obvious motivation for two paths through any finite-state grammar.

With phrase structure alone, it, “the growling of lions” and “the raising of flowers” are all the – V + ing – of – NP. Transformationally, T1 maps “lions growl” to “the growling of lions” and T2 maps “they raise flowers” to “the raising of flowers”; “hunters shoot” and “they shoot the hunters” are both kernel sentences, so “the shooting of the hunters” has two transformational origins.

A small, possibly finite kernel of basic sentences with phrase structure, plus transformations applied to kernel sentences or earlier transforms to produce more complicated sentences, reducing the problem of understanding a sentence partly to understanding kernel sentences.