Mathematical Methods in Linguistics

Main Units

Introduction

How to use these notes

Reading 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 (work in progress)

Summary of n-grams in linguistics

N-gram models of grammaticality (Solutions)

Positive n-gram grammars (Solutions)

Combining n-gram grammars (Solutions)

Succinctness and choosing between grammars (Solutions)

Making n-grams more powerful: Phonological tiers (Solutions)

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

The problem of overgeneration (Solutions)

Morphological paradigms (Solutions)

NPIs and monotonicity (Solutions)

Monotonicity in case syncretism (Solutions)

Person Case Constraints (Solutions)

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

Generalizing n-grams to mappings: a failed attempt (Solutions)

Finite-state transductions as a game (Solutions)

Finite-state transductions as transducers (Solutions)

Phonological processes as transductions (Solutions)

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

Factorial (Solutions)

Sets

Sets: The basics

Union, intersection, and complement of sets

Cardinality

Comparing sets

Set-builder notation

The Powerset

Sets: The basics (Solutions)

Union, intersection, and complement of sets (Solutions)

Comparing sets (Solutions)

Strings

Strings: Basic notation

Parts of strings

Strings: Basic notation (Solutions)

Tuples

Tuples: The basics

Crossproduct (aka Cartesian product)

Tuples: The basics (Solutions)

Functions

Functions: Basic notation

Function growth and Big O notation

Domains and co-domains

Monotonicity

Range and surjections

Functions: Basic notation (Solutions)

Domains and co-domains (Solutions)

Monotonicity (Solutions)

Relations

Relations: Basic notation

Order relations: the intuition

Partial orders

Linear orders (aka total orders)

Taking the closure of a relation

Types of relations

Relations: Basic notation (Solutions)

Partial orders (Solutions)

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