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, q0
- 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 languageL is regular if it is the language accepted by some DFA, and the DFA accepts only the strings in L.