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.

The transition function takes a state and an input symbol and returns a state, the state that the DFA will proceed to.

In proofs, an implication statement that is true because the "if" portion is false is said to be true vacuously.

A language L is regular if it is the language accepted by some DFA, and the DFA accepts only the strings in L.

Nondeterministic Finite Automata

Has the ability to be in several states at once.

δ takes a set of states that it could be in and produces a set of states it could be in given those states.

For any NFA there is a DFA that accepts the same language. The proof is the subset construction.

There's a lot in here, but it all boils down to DFAs where individual states represent sets of states in the NFA or ε-NFA.

Week 2

Regular Expression

RE's use three operations

• Union (+)
• Concatenation (no operator)
• Kleene star (*)

Union is simple. Concatenation produces a sort of cross product. The Kleene star is just the star - it represents any string in L.

Ø + R = R

εR = Rε = R

ØR = RØ = Ø

I missed something here, I may need to go through this again.