Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

How do a DFA Process Strings?

The important thing about DFA is to know that it identifies the acceptance of strings. 

A DFA processes a string by starting in the start state and reading the input symbols one at a time. For each input symbol, the DFA transitions to the next state according to the transition function, and it accepts the string if it ends in an accepting state.

An algorithm that describes how a DFA processes a string:

  1. Start in the start state.
  2. Read the next input symbol.
  3. Transition to the next state according to the transition function.
  4. If the current state is an accepting state, then accept the string.
  5. If the current state is not an accepting state, and there are no more input symbols to read, then reject the string.
  6. Repeat steps 2-5 until the end of the string is reached.

For example, 

Consider the DFA that identifies whether the given decimal is even or odd. 

Here we consider 3 states, one start state qstart, one even state qeven and one odd state qodd. 

If the machine stops at qeven the given number is even. 

If it stops at qodd the given number is odd.

References:

  • Introduction to the Theory of Computation” by Michael Sipser.