/
Finite Automata
Search
Duplicate
Notion
Finite Automata
Definitions
Deterministic Finite Automata: A $5$ï»¿-tuple $\{Q, \Sigma, \delta,q_0, F\}$ï»¿ where $\delta: Q \times \Sigma \to Q$ï»¿.
Language: $L \subseteq \{0, 1\}^*$ï»¿
Recognizing Language: If a machine $M$ï»¿ accepts all strings $\in L$ï»¿ and rejects every other string $\not\in L$ï»¿, then we say that $M$ï»¿ recognizes $L$ï»¿. Conversely, $L(M) =$ï»¿ language recognized by $M$ï»¿.
Regular Expressions: Uses $()\text{ braces},\ |\text{ union},\ *\text,\ \cdot\text{ concatenation}$ï»¿.
Non-deterministic Finite Automata: A $5$ï»¿-tuple $\{Q, \Sigma, \delta,q_0, F\}$ï»¿ where $\delta: Q \times \{\Sigma \cup \epsilon\} \to 2^Q$ï»¿.
Generalized NFA: A $5$ï»¿-tuple $\{Q, \Sigma, \delta,q_{start}, q_{accept}\}$ï»¿ where we have the following.
$\delta: \{Q - \{q_{accept}\}\} \times \{Q - \{q_{start}\}\} \to R\ (\text{Regex})$
Theorems on Finite Automation
â€¢
$L(\text{finite automata}) = \text{regular language}$ï»¿
â€¢
All finite languages are regular.
â€¢
Memory of a finite automata $= log_2 (|Q|) \sim O(1)$ï»¿
â€¢
Regular languages are closed under the union operation.
â€¢
Regular languages are closed under the concatenation operation.
â€¢
$\text{Regex} \equiv \text{DFA} \equiv \text{NFA}$ï»¿
â€¢
For a given NFA of n state, number of states in equivalent DFA is atmost $2^n$ï»¿. Worst case complexity is $O(2^n)$ï»¿.
â€¢
Conversion of NFA to DFA may require exponential increase in space. But $2^{O(1)} = O(1)$ï»¿.
Pumping Lemma
If $A$ï»¿ is a regular language then there is a number $p$ï»¿ where if $s$ï»¿ is any string in $A$ï»¿ of length at least $p$ï»¿ $(|s| \geq p)$ï»¿, then $s$ï»¿ may be divided into three pieces, $s = xyz$ï»¿, satisfying the following conditions:
1.
for each $i \geq 0,\ xy^iz \in A$ï»¿
2.
$\vert y \vert > 0$ï»¿
3.
$\vert xy \vert \leq p$ï»¿
Main Proof: $\text{Regex} \equiv \text{DFA} \equiv \text{NFA}$ï»¿