To my linguistics homepage

LING/C SC/PSYC 438/538
Computational Linguistics
Fall 2026

This is a introductory course in computational linguistics at an advanced level. No pre-requisites for graduate students, we will learn the rudiments of programming and the theoretical underpinnings of grammar systems from scratch.

Reference Textbook

Optional: Speech and Language Processing 2nd edition, by D. Jurafsky and J.H. Martin, Prentice-Hall 2008. Or 3rd edition PDF.

Software

All software used in this class will be freely available.
We will use Python, Perl and SWI-Prolog as programming languages.
The instructor reserves the right to ask students to install additional software necessary to do some homework exercises.

Instructor: Sandiway Fong sandiway@arizona.edu
Office: Douglass 308 (send email for an appointment or take a chance and drop by before class)

Administrivia

Location Social Sciences, Rm 411
Time Tuesdays/Thursdays 3:30PM - 4:45PM

Syllabus

See lecture1 slides.

Lecture Notes

Available in Adobe PDF and Microsoft Powerpoint .pptx formats.

August

Date Lecture Notes Number
of Slides
Panopto Topic
PDF Powerpoint
8/25 lecture1.pdf lecture1.pptx 39 Part 1: Viewer / Part 2: Viewer Administrivia and Introduction. Syllabus.
Homework 1: read PDF of chapter 1 of textbook for Homework 3 next time.here.
Homework 2: Install Perl and Python.
Some notes on programming languages. AI and coding.
8/27 lecture2.pdf lecture2.pptx 36 Viewer Language and computers: openai/whisper, assistive technologies and some limits.
Recursive nature of language.
Introduction to natural language analysis: syntactic structure. Parser demos, ChatGPT.
Homework 3

September

Date Lecture Notes Number
of Slides
Panopto Topic
PDF Powerpoint
9/1 lecture3.pdf lecture3.pptx 15 Viewer Homework 3 Review.
Guest presentation: Jeff Winkelman, Career Development & Employee Relations, Social & Behavioral Sciences
SBS Resume Building
9/3 lecture4.pdf lecture4.pptx 38 Viewer What is a Language Model: a look at text completion. English subject verb agreement. Oddities.
LLM: memorizing quotes. ChatGPT-2 to 5.
Beginning programming with Perl: focusing on proper use of quotes. QWERTY keyboard history. ChatGPT help.
world.perl / world.py
Homework 4: using GPT-2, Stanza and Berkeley Neural Parser.
9/8 lecture5.pdf lecture5.pptx 28 Viewer A note on submission dates
Homework 4 review and extensions: AI subword tokenization
A bit more on quoting.
Recommend installing WSL2 (Ubuntu) on Windows 11.
perlintro review: scalars and arrays.
9/11 lecture6.pdf lecture6.pptx 41 Viewer perlintro contd.
@ARGV array and some array operations.
Numeric and string equality. Coercion. Repetition. General looping: while, for, foreach. List range.
Useful string functions, including chomp and split. tr.
String length: bytes vs. characters (utf-8).
File I/O: open and <filehandle>.
Programs: myprog.perl / myprog.py
Program: read.perl
Example text file: falconheavylaunch.txt
Homework 5: two exercises.
Data files: 5letters.txt / 6letters.txt / 7letters.txt
9/15 lecture7.pdf lecture7.pptx 25 Viewer Homework 5 review. Scrabble word length statistics.
Worked Perl file I/O example. Split and summing the words. Word frequency table using hash tables.
Sorting in Perl, Python and on the command line.
Files: falconheavylaunch.txt
Terminal log: terminal7.txt
9/17 lecture8.pdf lecture8.pptx 30 Viewer Perl hash table recap and dict in Python. Anonymous arrays in Perl. Part of Speech dict example.
Homework 6 on spelling rules + disemvoweling.
Code: hw6template.perl
File: ppch1.txt (note: utf-8 character set)
9/22 lecture9.pdf lecture9.pptx 39 Viewer Homework 6 review.
Perl references. Perl Modules: CPAN. Date::Calc. cpanm command.
Python libraries timedate and locale.
Ungraded homework: install Lingua::EN::CMUDict, the CMU Pronouncing Dictionary.
File: dow.perl
9/24 lecture10.pdf lecture10.pptx 35 Viewer Ungraded Homework Review: Lingua::EN::CMUDict and Google AI!
Biased news reporting.
Homework 7: On media bias and headlines
Introduction to Perl regex.
9/29 lecture11.pdf lecture11.pptx 34 Viewer Homework 7 Review: on media bias and headlines
"The lines of code that changed everything"
Getting deeper into Perl regex:
Word boundaries \b, capture, backreferences, shortest vs. greedy matching, nondeterminism (backtracking).

October

Date Lecture Notes Number
of Slides
Panopto Topic
PDF Powerpoint
10/1 lecture12.pdf lecture12.pptx 26 Viewer Homework 8: regex and the FinCEN Files.
More on Perl regex: Perl code inside a replacement string in s/pattern/replacement/!
Character and word frequency counting
Zipf's Law: Brown Corpus case study
File: 12thnight.txt
Homework file: download_transactions_map.csv (1.1MB)
10/6 lecture13.pdf lecture13.pptx 28 Viewer Homework 8 review.
Perl regex: lookahead, lookbehind.
Predicate argument structure: Framenet. Propbank.
10/8 lecture14.pdf lecture14.pptx 27 Viewer Ungraded Regex Homework
Stanford CoreNLP. Stanford dependencies and Universal Dependencies (UD). ChatGPT and syntax.
Relative clauses and Perl regex.
10/13 lecture15.pdf lecture15.pptx 30 Viewer Extra: ChatGPT 5 on the center-embedding cases
Regex recursion and center-embedding.
Prime number testing using Perl regex (backreferences).
Slides updated: 4:45pm
10/15 lecture16.pdf lecture16.pptx 22 Viewer Homework 10: regex recursion
Introduction to Finite State Automata (FSA).
Note: slides updated 4:40pm
10/21 lecture17.pdf lecture17.pptx 24 Viewer Homework 10 review
regex example: Einstein on xkcd simplewriter
FSA contd.: formal definition, Perl and Python implementations revisited.
e-transitions, and single vs. multiple start states.
Non-deterministic FSA (NDFSA). NDFSA to DFSA conversion.
File: fsa.perl
10/22 lecture18.pdf lecture18.pptx 15 Viewer Non-deterministic FSA (NDFSA). NDFSA to DFSA conversion again. Two worked examples.
Markov Chains. Case of Eugene Onegin.
Homework 11. Note: Q5 is not optional for 538.
File: Hayes 2013
10/27 lecture19.pdf lecture19.pptx 23 Viewer Homework 11 review.
Regular Languages and closure properties.
Turing Machines (TMs), a useful digression.
Programming a TM: +1, +2, doubling.
Terminal log: terminal19.txt
Slides updated: 4:50pm
10/29 lecture20.pdf lecture20.pptx 15 Viewer Example of a machine is (perhaps) easier to build than a regex.
The state bypass method: converting a FSA into a regex algorithmically
Homework 12

November

Date Lecture Notes Number
of Slides
Panopto Topic
PDF Powerpoint
11/3 lecture21.pdf lecture21.pptx 38 Viewer Announcement: class schedule for the remainder of the semester
538 Presentations: announcement
Homework 12 review.
Beyond regular languages: {anbn | n ≥ 1} and {1n | n is prime}.
A formal tool: the Pumping Lemma for regular languages.
Slides updated: 5pm
11/5 lecture22.pdf lecture22.pptx 23 Viewer Homework 13. Install SWI-Prolog.
A quick introduction.
Recursive definitions. Non-determinism and backtracking. Language enumeration.
Some example Prolog programs:
test.prolog
N!: factorial.prolog
N!: factorial2.prolog
Σ*: sigmastar.prolog
Terminal log: terminal22.txt
Slides updated: 4:50pm
11/10 lecture23.pdf lecture23.pptx 27 Viewer 538 Presentations list
Contd. from last time
Recursion: Control of backtracking using fail and cut.
Built-in predicates: length/2 and findall/3.
set_prolog_flag for answer reporting: answer_write_options.
The Chomsky hierarchy: (type-3) regular grammars. The definite clause grammar (DCG) formalism.
Regular grammars in Prolog. Tree representation. Prolog's default computation rule. Top-down and bottom-up derivations.
The correspondence between right recursive regular grammars and FSA.
Example type-3 DCG: apbp.prolog
bb+ grammar: bbp.prolog
Grammar: bab.prolog
Terminal log: terminal23.txt
Slides updated: 5:30pm
11/12 lecture24.pdf lecture24.pptx 34 Viewer REMINDER: 538 Presentations!
From last time: right recursive regular grammar and FSA.
Grammar: bab.prolog
Breadth-first search vs. depth-first search: iterative deepening.
Beyond regular languages: left and right recursive rules.
Using an extra argument to return a parse tree.
Grammar: anbn.prolog
Grammar: anbn2.prolog
A brief note on expressive power and extra arguments.
Left recursion, set enumerate and infinite loops.
Grammar: lrrg.prolog
Terminal log: terminal24.txt
Homework 14
Slides corrected: 4:55pm
11/17 lecture25.pdf lecture25.pptx 27 Viewer REMINDER: 538 Presentations next week!
Homework 14 Review
Using an extra argument to return a parse tree.
Grammar: anbn.prolog
Grammar: anbn2.prolog
A brief note on expressive power and extra arguments.
Left recursion, set enumerate and infinite loops.
Grammar: lrrg.prolog
Extra arguments and context sensitivity, the case of {anbncn | n ≥ 1}.
abc.prolog
abc2.prolog
Slides updated: 5:30pm
11/19 lecture26.pdf lecture26.pptx Viewer Last opportunity to give out a homework.
11/24 lecture27.pdf lecture27.pptx 3 Viewer 538 Presentations: part 1
11/26 Viewer Thanksgiving - no classes

December

Date Lecture Notes Number
of Slides
Panopto Topic
PDF Powerpoint
12/1 lecture28.pdf lecture28.pptx 3 Viewer 538 Presentations: part 2
12/3 Away - no classes
12/8 Away - no classes


To my linguistics homepage
Last modified: Tue Nov 17 17:20:22 MST 2026