/
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.
RegexDFANFA\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 (sp)(|s| \geq p), then ss may be divided into three pieces, s=xyzs = xyz, satisfying the following conditions:
1.
for each i0, xyizAi \geq 0,\ xy^iz \in A
2.
y>0\vert y \vert > 0
3.
xyp\vert xy \vert \leq p
Main Proof: RegexDFANFA\text{Regex} \equiv \text{DFA} \equiv \text{NFA}