The given finite automaton is equivalent to which of the following regular…

Concept: A finite automaton accepts exactly those strings that can be spelled out along some path from the start state to an accepting state. Turning such a diagram into a regular expression rests on three correspondences: consecutive edges along one path become concatenation, alternative routes become a union (+), and a self-loop that carries every alphabet symbol becomes (a + b)*. When a state has two edges on the same symbol the machine is non-deterministic, so a string is accepted as soon as one route works, and the whole language is the union taken over all start-to-accepting routes.

Application: In this diagram the start state q0 branches on a to q1 and to q4, and on b to q5; the state q2 carries a self-loop labelled a, b; and qf is the only accepting state. Every route from q0 to qf therefore has one of three shapes.

1. q0 —a→ q1 —b→ qf spells the string ab.

2. q0 —a→ q4 —a→ q2, then the a, b self-loop on q2 any number of times, then q2 —b→ qf spells aa (a + b)* b.

3. q0 —b→ q5 —b→ q2, then the same self-loop, then q2 —b→ qf spells bb (a + b)* b.

Taking the union of the three shapes and factoring out the shared (a + b)* b tail gives ab + aa (a + b)* b + bb (a + b)* b = ab + (aa + bb) (a + b)* b.

Cross-check: Test the result against the diagram on concrete strings: ab is accepted; aab is accepted through q0, q4, q2, qf; aaab is accepted by looping once on q2; baa is rejected because q5 has no edge on a; and no accepted string of length two or more ends in a, because every edge entering qf carries the label b.

Contrast with the other patterns:

• (a + b)* (aa + bb) (a + b)* denotes every string that contains aa or bb somewhere, so it takes in aa and baa, which the diagram does not accept.

• ab (aa + bb) (a + b)* b forces the two symbols ab in front of the double letter, so it leaves out aab and aaab, which the diagram does accept.

• ab (aa + b) (a + b)* a ends every string it denotes with a, while every edge entering qf carries the label b.

The regular expression equivalent to the given finite automaton is therefore ab + (aa + bb) (a + b)* b.