Recognizing Simple Languages
This screencast introduces the regular languages, the simplest level in the Chomsky hierarchy of languages and their corresponding computational systems. Regular languages are sets of strings recognized by many equivalent systems, including the regular expressions that we use in everyday programming. We begin with a simple regular expression, gradually transforming it into a regular grammar, and then into a finite state machine. This shows the relationship between these three systems, and also hints at one method of implementing regular expression engines.