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

Deterministic Finite Automata

An alphabet is any finite set of symbols, such as letters and is represented as Σ

A string over an alphabet Σ is a list where each element is a member of Σ

Σ* = set of all strings over alphabet Σ

Ε stands for the empty string.

A language is a subset of Σ* for some alphabet Σ.

Deterministic Finite Automata

• A finite set of states, Q
• An input alphabet, Σ
• A transition function δ
• A start state, q₀
• A set of final (or accepting) states, F where F ⊆ Q.