🌽
Algorithms and Theory
/
Finite Automata
Search
Duplicate
Notion
Finite Automata
Definitions
Deterministic Finite Automata: A 55-tuple {Q,Σ,δ,q0,F}\{Q, \Sigma, \delta,q_0, F\} where δ:Q×Σ→Q\delta: Q \times \Sigma \to Q.
Language: L⊆{0,1}∗L \subseteq \{0, 1\}^*
Recognizing Language: If a machine MM accepts all strings ∈L\in L and rejects every other string ∉L\not\in L, then we say that MM recognizes LL. Conversely, L(M)=L(M) =  language recognized by MM.
Regular Expressions: Uses () braces, ∣ union, ∗, ⋅ concatenation()\text{ braces},\ |\text{ union},\ *\text,\ \cdot\text{ concatenation}.
Non-deterministic Finite Automata: A 55-tuple {Q,Σ,δ,q0,F}\{Q, \Sigma, \delta,q_0, F\} where δ:Q×{Σ∪ϵ}→2Q\delta: Q \times \{\Sigma \cup \epsilon\} \to 2^Q.
Generalized NFA: A 55-tuple {Q,Σ,δ,qstart,qaccept}\{Q, \Sigma, \delta,q_{start}, q_{accept}\} where we have the following.
δ:{Q−{qaccept}}×{Q−{qstart}}→R (Regex)\delta: \{Q - \{q_{accept}\}\} \times \{Q - \{q_{start}\}\} \to R\ (\text{Regex})
Theorems on Finite Automation
•
L(finite automata)=regular languageL(\text{finite automata}) = \text{regular language}
•
All finite languages are regular.
•
Memory of a finite automata =log2(∣Q∣)∼O(1)= log_2 (|Q|) \sim O(1)
•
Regular languages are closed under the union operation.
•
Regular languages are closed under the concatenation operation.
•
Regex≡DFA≡NFA\text{Regex} \equiv \text{DFA} \equiv \text{NFA}
•
For a given NFA of n state, number of states in equivalent DFA is atmost 2n2^n. Worst case complexity is O(2n)O(2^n).
•
Conversion of NFA to DFA may require exponential increase in space. But 2O(1)=O(1)2^{O(1)} = O(1).
Pumping Lemma
If AA is a regular language then there is a number pp where if ss is any string in AA of length at least pp (∣s∣≥p)(|s| \geq p), then ss may be divided into three pieces, s=xyzs = xyz, satisfying the following conditions:
1.
for each i≥0, xyiz∈Ai \geq 0,\ xy^iz \in A
2.
∣y∣>0\vert y \vert > 0
3.
∣xy∣≤p\vert xy \vert \leq p
Main Proof: Regex≡DFA≡NFA\text{Regex} \equiv \text{DFA} \equiv \text{NFA}