Automata itself is a very interesting thesis and Turing Machines which Automata leads to are breathtakingly beautiful.

The Finite Automata part is taught by the Stanford University here but is a little tedious, and the rest part is taught by UC Davis as ECS120 and videos can be found here, the latter UC Davis course is much easier to understand and a lot of fun.

# Introduction

When developing solutions to real problems, we often confront the limitations of what software can do.

• Undecidable things – no program whatever can do it.
• Intractable things – there are programs, but no fast programs.

# Finite Automata

What is a Finite Automaton?

• A formal system.
• Remembers only a finite amount of information.
• Information represented by its state.
• State changes in response to inputs.
• Rules that tell how the state changes in response to inputs are called transitions. Acceptance of Inputs

• Given a sequence of inputs (input string ), start in the start state and follow the transition from each symbol in turn.
• Input is accepted if you wind up in a final (accepting) state after all inputs have been read.

Language of an Automaton

• The set of strings accepted by an automaton A is the language of A.
• Denoted L(A).
• Different sets of final states -> different languages.
• Example: As designed, L(Tennis) = strings that determine the winner.

Nondeterminism

• A nondeterministic finite automaton has the ability to be in several states at once.
• Transitions from a state on an input symbol can be to any set of states.
• Start in one start state.
• Accept if any sequence of choices leads to a final state.
• Intuitively: the NFA always “guesses right.” Equivalence of DFA’s, NFA’s

• A DFA can be turned into an NFA that accepts the same language.
• If δD(q, a) = p, let the NFA have δN(q, a) = {p}.
• Then the NFA is always in a set containing exactly one state – the state the DFA is in after reading the same input.
• Surprisingly, for any NFA there is a DFA that accepts the same language.
• Proof is the subset construction.
• The number of states of the DFA can be exponential in the number of states of the NFA.
• Thus, NFA’s accept exactly the regular languages.

Subset Construction

• Given an NFA with states Q, inputs Σ, transition function $δ_N$, state state $q_0$, and final states F, construct equivalent DFA with:
• States $2^Q$ (Set of subsets of Q).
• Inputs Σ.
• Start state ${q_0}$.
• Final states = all those with a member of F.
• The transition function δD is defined by: $δ_D({q_1,...,q_k}, a)$ is the union over all i = 1,…,k of $δ_N(q_i, a)$. # L2: Regular Languages and Non-Deterministic FSMs

A DFA is an NFA, but not every NFA is a DFA.

Theorems:

• Every DFA has an equivalent NFA.
• Every NFA has an equivalent DFA.

Regular Language

A Language that is recognized by some DFA (DFSM) is called a regular language.

Theorems:

• If A and B are regular, then $A \cup B$ is regular. Here is proof
• If A and B are regular, then $A \cap B$ is regular.
• If A and B are regular, then $A \circ B$ is regular. (Concatenation)

# L4: Regular Expression

A regular expression R is:

1. a for some $a \in \Sigma$
2. $\epsilon$, the empty string
3. $\Phi$, the empty set
4. $(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions
5. $(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions
6. $(R_1^*)$ where $R_1$ and $R_2$ are regular expressions
• $R \circ \Phi \equiv \Phi$ because empty set is equivalent to an NFA which doesn’t accept any string.
• $\Phi^* \equiv \left\{\epsilon \right\}$ .
• $R \cup \Phi \equiv R$ .
• $R \circ \epsilon \equiv R$ .
• $R \cup \epsilon \equiv R$ if and only if R contains empty string.

Theorem: A language is regular if and only if it is described by some regular expressions. # L5: Regular Expressions, Regular Languages and Non-Regular Languages

Non-Regular Languages

A string set like this $\left\{ 0^n1^n : N \ge 0 \right\}$ can’t be recognized by a DFA, thus not a regular language.

# L6: The Pumping Lemma and Introduction to CFLs

Pumping Lemma:

If A is a regular language, there is a number p (the pumping length) so that if w ∈ A and |w| ≥ p, then w may be divided into three substrings w = xyz, satisfying the conditions:

1. for all i∈N, $xy^iz∈A$,
2. |y| > 0, and
3. |xy| ≤ p.