Skip to content

DFSA V.S. NDFSA

Jump to bottom
pavl_g edited this page Aug 10, 2023 · 8 revisions

There are two common forms of State-Machines, the first one is known as the deterministic Finite-State-Automaton, which involves only and only a single determined successor transition path between each 2 states. Moreover, a transition must be specified for each input value.

The second one is known as the non-deterministic Finite-State-Automaton, which involves other alternative ways of defining transition paths including but not limited to, multiple successor paths, and no input value for a transition (null-transitions).

  • E.g:

image

Notes:

  • Starting states are marked by this arrow ->.
  • Terminating states (aka. accepting states) are marked by double circles.
  • A valid recognizable pattern can be instantiated by starting from an arrow state -> and finishing at a double-circled state.

Examples of the recognizable patterns by this NDFSA:

  • 1110, in the following path: > Start -> A -1-> B -1-> D -1-> C -0-> A -> End <
  • 11011, in the following path: > Start -> B -1-> D -1-> C -0-> B -1-> D -1-> C -> End <
  • 1111, in the following path: > Start -> A -1-> B -1-> A -1-> B -1-> A -> End <
  • 11111, in the following path: > Start -> A -1-> B -1-> A -1-> B -1-> D -1-> C -> End <
  • 111, in the following path: > Start -> A -1-> B -1-> D -1-> C -> End <
  • And so on...

This NDFSA state transition graph rejects the following patterns:

  • 100
  • 0001
  • 1000
  • 10000
  • 10
  • And any other patterns that have invalid paths using this NDFSA.

NDFSA helps to build simpler transition graphs, in which any rule can be applied and states can have more than one successor transition and even multiple input values.

NDFSA adds the value to easily define recognizable patterns (e.g: set of strings, or even a set of solutions to a logical system), a recognizable pattern is defined by following one of the valid paths defined by this FSA state diagram, thus a single NDFSA pattern can define a subset of recognizable patterns (think of a game state with a tweakable subset of sequential actions).

On the other hand, DFSA has a verbose and strict logic pattern, however, both provide equivalent values and conversion between both can be done easily, in the next chapter, we will discuss some good techniques to convert from a NDFSA to a DFSA; because DFSA is direct, verbose and strict and usually simple in its transitions, sometimes it's feasible.

DFSA V.S. NDFSA:

Clone this wiki locally