Um Automato Finito Nao-deterministico N eh uma tupla: $$M = (Q, \Sigma, \delta, q_{0}, F)$$

  • $Q =$ Conjunto de estados
  • $\Sigma =$ Alfabeto de entrada
  • $\delta=$ função programa/função de transição
  • $q_{0}=$ Estado Inicial ($q_{0}\in Q$)
  • $F =$ Estados finais ($F \subset Q\times{\epsilon }$) // conjunto das partes de $Q$

diferencas:

  • transicao pode ter a cadeia vazia.
  • pode-se haver 2 transicoes com o mesmo simbolo do alfabeto e estados como entrada.
  • definicao formal:
    • $\delta (q_{i}, a) = {q_j}$
    • $\delta (q_{i}, \epsilon) = {q_j}$
  • tabela de transicao:
$v_0$$v_1$$\dots$$v_n$
-> $q_0$${q_4}$${q_4}$$\vdots$$\vdots$
$\underline{q_1}$${q_4}$$\vdots$$\vdots$
$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$
$q_n$$\dots$$\dots$$\dots$$\vdots$