Automata Course

Video Lectures

Week 1

Course Outline and Motivation

One of the highest ranked courses at Standford for "most used" after 5 years of employement.

Used in regex and modeling electronics. We will cover context-free grammars.

Some problems are undecidable or intractable and automata can help identify them and help avoid sinking time into them.

We will look at

• Regular languages
• Context-free languages
• Recursively enumerable languages

Informal Introduction to Finite Automata

What is a finite automata

• a formal system
• remembers only a finite amount of information
• information represeted by state
• state changes in response to inputs
• rules that tell how the state changes in response to inputs are called transitions

Why Study them?

• used for design and verification
• used for many text - processing
• important component of comilers
• describes simple patterns of events