Finite State Machines and Regular Languages: An Introduction to the Chomsky Hierarchy

Curran McConnell
Thursday, October 20 at 4:30 pm
Ross N638

The Chomsky hierarchy is a correspondence between various classes of languages and various classes of machines, arranged according to their grammatical/mechanical complexity. I will introduce this hierarchy, and give concrete examples from the layer including regular languages and finite-state machines. I will then outline some reasons why one might require a machine more complex than a finite-state machine. If time permits, I will share some amusing limitations of this theory vis-a-vis computer languages & machines found "in the wild".