The Little Book of Language, Math, and Computation

Main Units

Introduction

How to read this book

Supplementary readings, or: What’s unique about this book?

How to read mathematics

Mathematical elegance

N-grams for linguistics

N-gram models of grammaticality

Analyzing negative n-gram grammars

Formal definition and proof of the normal form theorem

Positive n-gram grammars

Proof: Equivalence of positive and negative grammars

Combining n-gram grammars

Succinctness and choosing between grammars

Making n-grams more powerful: Phonological tiers

The mathematics of tiers

Different ways of thinking about tiers

Summary of n-grams in linguistics

Extra exercises on n-grams

N-grams in language technology (optional)

An n-gram model of text

Set-of-words revisited: adding counts

Dealing with stop words

Stop word removal as a function

Universals and monotonicity

What’s to come, and what you should know already

The problem of overgeneration

Morphological paradigms

NPIs and monotonicity

Monotonicity in case syncretism

Person Case Constraints

Explaining a syntactic universal: the Adjunct Island Constraint

The lattice space of n-gram grammars

Summary of monotonicity and universals

Mappings

What’s to come, and what you should know already

Generalizing n-grams to mappings: a failed attempt

Finite-state transductions as a game

Finite-state transductions as transducers

Phonological processes as transductions

Rule ordering via cascades and composition

From surface forms to underlying representations: phonological parsing

The generative capacity of finite-state transducers

Transducers VS automata

Local transductions

More fun with finite-state machinery

Two-level morphology

Optimization and violable constraints

Finite-state recognition as Boolean matrix multiplication

Matrix multiplication for harmonic grammar

Background

General Background

Common abbreviations

Notation: Big operators

Equals VS Define: Why = is not the same as :=

Exponentiation

Factorial

Picking maxima and minima

Sets

Sets: The basics

Operations: Union, intersection, and complement of sets

Cardinality

Comparing sets

Set-builder notation

The Powerset

Strings

Strings: Basic notation

Parts of strings

Tuples

Pairs

Tuples: The basics

Crossproduct (aka Cartesian product)

The Kuratowski definition of pairs

Functions

Functions: Basic notation

Function growth and Big O notation

Domains and co-domains

Monotonicity

Range and surjections

Relations

Relations: Basic notation

Order relations: the intuition

Partial orders

Linear orders (aka total orders)

Taking the closure of a relation

Types of relations

Posets

Partially ordered sets (posets)

Lower bounds and upper bounds

(Semi)Lattices

Linear algebra

Vectors

Dot product of vectors

Matrices and matrix multiplication

Additional practice exercises

Practice exercises for n-gram grammars

1000 automatically generated exercises with n-gram grammars

Practice exercises for set operations

Exercises with set operations (Batch 1)

Exercises with set operations (Batch 2)

Exercises with set operations (Batch 3)