Nondeterministic finite automaton: Difference between revisions

Revision as of 10:25, 23 January 2025

Revision as of 19:09, 28 January 2025

Line 28:

An ''NFA'' is represented formally by a 5-[[tuple]],

<math>(Q, \Sigma, \delta, q_0, F)</math>, consisting of

* a finite [[Set (mathematics)|set]] of [[State (computer science)|states]] <math>Q</math>,

* a finite set of input symbols called the [[inputAlphabet (computer symbolscience)|alphabet]]s <math>\Sigma</math>,

* a transition [[function (mathematics)|function]] <math>\delta</math> : <math>Q\times \Sigma \rightarrow \mathcal{P}(Q)</math>,

* an ''initial'' (or ''start'') state <math>q_0 \in Q</math>, and

* a set of states <math>F</math> distinguished as ''accepting'' (or ''final'') ''states'' <math>F \subseteq Q</math>.

Here, <math>\mathcal{P}(Q)</math> denotes the [[power set]] of <math>Q</math>.