What is a transition graph (TG)?

A finite automaton (FA) processes an input string one letter at a time. But what if we wanted a more capable machine that could read multiple letters of the input string at a time and change its state based on that? Transition graphs offer a solution to this problem.

A transition graph (TG) is a type of FA used to provide a visual representation of states, input symbols, and transitions. Unlike an FA, a TG also allows for multiple start states and for an edge to have a null string. It allows for a clear understanding of how input strings are processed to determine the acceptance of a language.

Note: Each finite automaton can be visualized as a transition graph; however, the opposite is not always true.

A TG is a collection of the following:

1. A finite set of input letters $Σ$ from which input strings are formed.

2. A finite number of states $Q$, at least one of which is the start state $S$and some (maybe none) final states (or accepting states) $F$.

3. A finite set of transitions $δ$(or edge labels) that show how to go from one state to another based on reading specified substrings of input letters, possibly even the null string $Λ$.

Syntax

Let a transition graph $T=(Q, Σ, S, F, δ)$:

• A successful path in $T$starts with a start state $S$and ends with the final state $F$.

• Let $P$ be the set of all successful paths in $T$.

• Let $L$ be the set of words that are the concatenation of the sequence of edge labels of $T$corresponding to a successful path in $T$.

• $L(T) = L$ denotes the language accepted by $T$.

Note: Given a transition graph $A$, it’s unclear how to determine $L(A)$.

Example

Consider the language $L$ such that:

• It’s defined over $Σ=${$a,b$}

• It consists of strings that begin and end with different letters

• All strings have $length\ge2$

$L$ can be expressed by the following regular expression: $a(a + b)*b + b(a + b)*a$.

1. Begin at the start state $1-$

2. If the first letter in the input string is:

   1. $a$, we’ll move to state $2$

   2. $b$, we’ll move to state $3$

3. The current state will persist until the second last letter of the input string is read

4. The last letter for the input string will be:

   1. $b$, for state $2$

   2. $a$, for the state $3$

5. The final state will be:

   1. $4+$, coming from state $2$

   2. $5+$, coming from state $3$

A successful path through a TG isn’t determined by the input alone. Human choice is also a factor in selecting the path, and the machine doesn’t independently make all the determinations. In the example above, there’s no counter to compare the position of the current letter with the last letter; we continue to stay on state $2$/state $3$ until we reach the last letter in the string and then manually move to state $4$/state $5$. Due to this dependence on human choice, we say that TGs are nondeterministic.

Note: A string is considered accepted by the machine if there exists at least one sequence of choices that results in a path leading to a final state.

FA to TG

Consider the language $L$ such that:

• It’s defined over $Σ=${$a,b$}

• It consists of strings that end in $b$

• All strings have $length\ge1$

Let’s create an FA and a TG that accepts $L$.

A finite automaton can have one letter per edge label.

We begin at the start node and stay in the same state until$b$occurs. We stay at the second node, which is the final state represented by until a occurs; the word will only be accepted if$b$occurs at the end.

A transition graph can have multiple letters per edge label. In this case, one of the edge labels in the TG contains two letters that help reduce the overall complexity (as seen in the FA).

We begin at the start node and stay in the same state until the last$b$occurs; at the last$b$, the word will be accepted by the TG and we’ll move on to the final state.

However, it’s important to be vigilant, as there’s a possibility that the TG might encounter issues if we make the mistake of traversing the non-loop edge label too soon.

Quiz

Attempt the quiz to test your knowledge of transition graphs.