NFA

definition

$${\Sigma }^{\ast }:\text{set of all strings based off }\Sigma$$ $$\begin{array}{rl}\text{NFA}M& =(Q,\Sigma ,\Delta ,S,F)\\ Q& :\text{finite set of states}\\ \Sigma & :\text{finite alphabet}\\ \Delta & :Q\times \Sigma \to P(Q)\\ S& :\text{Start states},S\subseteq Q\\ F& :\text{Final states},F\subseteq Q\\ & \end{array}$$

examples

1. $\mathcal{L}(M)=\{abxba\mid x\in {\Sigma }^{\ast }\}$

stateDiagram-v2
  direction LR
  [*] --> 0
  0 --> 1 : a
  1 --> 2 : b
  2 --> 2 : a, b
  2 --> 3 : b
  3 --> 4 : a
  4 --> [*]

2. $\mathcal{L}(M)=\{yx\mid x=00\vee x=11\wedge y\in {\Sigma }^{\ast }\}$

stateDiagram-v2
  direction LR
  [*] --> 1
  1 --> 1 : 0,1
  1 --> 2 : 0
  2 --> 3 : 0
  3 --> [*]
  1 --> 4 : 1
  4 --> 3 : 1

$ϵ$ transition

graph LR

  s((*)) --> s1{{s1}} --"1"--> s2{{s2}} --"1"--> s3{{s3}} --"e"--> s4{{s4}}
  s1{{s1}} --"e"--> s4{{s4}}
  s1{{s1}} --"0"--> s1{{s1}}
  s3{{s3}} --"1"--> s3{{s3}}

---

Given the following $M$

graph LR

  s((*)) --> s1{{s1}} --"1"--> s2{{s2}} --"1"--> s3{{s3}} --"e"--> s4{{s4}}
  s1{{s1}} --"e"--> s4{{s4}}
  s1{{s1}} --"0"--> s1{{s1}}
  s3{{s3}} --"1"--> s3{{s3}}

$\mathcal{L}(M)=\{0^n{1}^m\mid n\ge 0,m\ne 1,x\in {\Sigma }^{\ast }\}$