Finite Automata

Definitions

Alphabet: $\Sigma$ is a non-empty, finite set of symbols
String: $w$ over $\Sigma$ is a finite $(>0)$ sequence of symbols
- Empty String: $\epsilon \in \Sigma^*$
Set of All Strings: $\Sigma^*$ (an infinite set of strings)
Language: $L\sub\Sigma^*$ (infinite set of strings)
- Complement of $L$: $\bar{L}=\Sigma^* \backslash L$
- Concatenation of $A,B$: $AB=\{ab:a\in A,b\in B\}$
- $L^n=\{l_0,l_1,\dots,l_{n-1}|l_0,\dots,l_{n-1}\in L\}$ $L^0=\{\epsilon\}$ $L^1=L$
- Kleene Star: $L^=U_{i\in\N}L^i$ $\forall L \sub \Sigma^, \epsilon \in L^*$

Regular: There exists a DFA for the language.

Closure: Suppose $A,B$ are regular languages, then: $\bar{A},AB,A \cup B, A \cap B, A^n, A^*$ are also regular
$\forall w \in \Sigma^*,L=\{w\}$ is regular

Input: A string $w \in \Sigma^*$
Output: accept / reject
Starts at a predefined start state. Read chars one at a time, deterministically move to a new state depending on the char After reading the entire string, return accept if the state is an accept state, or else reject.
E.g. Odd number of 1s
Deterministic: The same input produce the same output
Finite: Finite number of states

Language of DFA: Let $M$ be DFA, the language of $M$ is $L(M)=\{w|w\in\Sigma^*, M \text{ accepts } w\}$