4. State transition diagrams

State transition diagrams

State transition diagram

We can represent the hard-wired control device of a finite automaton by a directed multigraph:

• with the vertices representing the states
• arrow-edges being labelled by symbols of the input alphabet
• the initial state is marked by $>$
• the favourable states are double-circled
• each arrow represents a possible transition, hard-wired in the control device: an arrow from state $q$ to state $r$ labelled by symbol $a$ indicates that, when the head is reading $a$ and the control device is in state $q$ then it should move next to state $r$

Link to original

Automaton $A_1$

digraph {
	label=A₁
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	s->s [label=a]
	s->q [label=b]
	q->q [label=b]
	q->r [label=a]
	r->r [label=a]
	r->r [label=b]
}

Input 1: $abba$ Computation: $(s,abba),(s,bba),(q,ba),(q,a),(r,ϵ)$ $⇝$ word $abba$ is rejected

Input 2: $aabb$ Computation: $(s,aabb),(s,abb),(s,bb),(q,b),(q,ϵ)$ $⇝$ word $aabb$ is accepted

Input 3: $bbaaa$ Computation: $(s,bbaaa),(q,baaa),(q,aaa),(r,aa),(r,a),(r,ϵ)$ $⇝$ word $bbaaa$ is rejected

Input 4: $bbb$ Computation: $(s,bbb),(q,bb),(q,b),(q,ϵ)$ $⇝$ word $bbaaa$ is accepted

Input 5: $ϵ$ Computation: $(s,ϵ)$ $⇝$ word $bbaaa$ is rejected