Non-deterministic finite automata

A non-deterministic finite automata is a tuple $(\mathcal{X},\mathcal{Q},q_i,F,\delta )$ where:

• $\mathcal{X}$ is an alphabet (finite set of atomic symbols)
• $\mathcal{Q}=\{q_0,q_1,\dots ,q_n\}$ is a finite set of states
• $q_i\in \mathcal{Q}$ is the initial state
• $F\subseteq \mathcal{Q}$ is the set of accepting states
• $\delta :\mathcal{Q}\times (\mathcal{X}\cup ϵ)\to \mathcal{P}(\mathcal{Q})$ is the transition function
  • $\mathcal{P}(\mathcal{Q})$ is the power set of $\mathcal{Q}$
  • $ϵ$ is an empty transition label that can be taken at any point when reading a word

A word is accepted if there is any trace from the initial state to an accepting state.