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

Notations for DFA

Transition Diagram: 

  • This is a graph in which vertices represent state of machine and the edges show transition of states.
  • The labels on these edges indicate input/output for the corresponding transition. 

A transition diagram for a DFA M = (Q, Σ, δ, q0, F) is a graph defined as follows:

  • For each state in Q there is a node. 
  • There is labelled input symbol on transition. 
  • Then the transition diagram has an arc (arrow) from one node to another node. 
  • If multiple input symbols cause the same transition from one node to another node, then multiple input labels separated by the commas are given to that edge. 
  • There is an arrow into the start state q0 labeled as start. This arrow does not originate at any node. 
  • Final states/ accepting states are marked by concentric double circles. 
  • States not belonging to final states have a single circle. e.g.

Transition Table:

  • It specifies the resultant set of states for the corresponding current state and input to the machine.
  • A transition table is a conventional tabular representation of a function like δ that takes two arguments and returns a value the rows of the table correspond to the states and the columns correspond to the inputs. 
  • The entry for the row corresponding to state q and the column corresponding to input q is the state δ(q, a).