learn.ifs.name

Three Models for the Description of Language

Chomsky, 1956, Three Models for the Description of Language (IRE Transactions on Information Theory)

Subscriber deck — free during early access

10 cards in “2 Finite state Markov processes” · whole deck

2 Finite state Markov processes

  1. How does a finite-state grammar generate a sentence?
    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.
  2. Define an \((i, j)\)-dependency in a sentence.
    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\).
  3. What necessary condition for finite-state languages does Chomsky prove?
    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.
  4. Give Chomsky’s three non-finite-state languages.
    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.
  5. Why is English not a finite-state language?
    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\).
    IfeitherS3,orS4,thenS2
    Dependencies nest like \(a^n b^n\), to any depth
  6. Why not just assume English sentences have a maximum length, making English finite-state?
    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.
  7. What is an \((n{+}1)\)th-order approximation to English, and why did some take it as a model of linguistic structure?
    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.
  8. What does “colorless green ideas sleep furiously” show?
    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.
  9. What happens to grammatical and ungrammatical strings as the order \(n\) of statistical approximation increases?
    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.
  10. Is every finite-state process an \(n\)th-order approximation?
    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.

Source

  • Noam Chomsky. 1956. Three Models for the Description of Language. In IRE Transactions on Information Theory, pp. 113–124. doi:10.1109/TIT.1956.1056813