Chapters

1 Introduction

2 Models of Computation

3 Recursion

4 Well-Formed Sentences and Grammaticality

5 Formal Languages

6 Universal Grammar and Classes of Formal Languages

7 Infinite Languages and Recursion

8 Distributions over Languages

9 Models and Data

10 Discrete Random Variables

11 Bag-of-Words Models

12 Maximum Likelihoood

13 Smoothing

14 Principles of Inductive Inference

15 Independence, Marginalization, and Conditioning

16 Hierarchical Models

17 Balancing Fit and Generalization

18 Inference Using Conditionalization

19 Dependencies between Words

20 Strictly-Local Languages, Formal Hierarchies, and Weak Generative Capacity

21 N-gram Models

22 Abstract Characterizations

23 Latent Structure

24 Hidden Markov Models

25 The Forward Algorithm

26 The Backward Algorithm

27 Finite-State Automata

28 The Myhill-Nerode Theorem

29 Determinism and Non-Determinism

30 Parsing and Inference

31 The Viterbi Algorithm

32 Bayesian Parsing Methods

33 Exact Sampling and Scoring

34 Parameter Estimation and Learning

35 Expectations

36 The Baum-Welch Algorithm

37 Expectation Maximization

38 Gibbs Sampling

39 Markov Chain Monte Carlo

40 Heads and Dependents

41 Context-Free Grammars

43 Parsing Context-Free Grammars

44 Parsing as Deduction

45 Chomsky Normal Form and CYK Parsing

46 Semirings

47 Viterbi and Inside Parsing for CFGs

48 Agenda-Based Chart Parsing

48 Parameter Estimation for CFGs

49 The Pumping Lemma for CFLs

50 Natural Languages and Context-Free Languages

51 Adjunction