🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q (a set of states) q 0 q_0 The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input Multiple transitions possible No ε-transitions ε-transitions allowed Deterministic ...
Comments
Post a Comment