COS2601 Assignment 03
Semester 1/2 2021
, Question 1
Kleene’s theorem can be used to turn a transition graph (TG) into a regular expression. Which one of the
following regular expressions would generate a language that would be equivalent to the language
described by the following TG?
1. aab*a + bba*
2. (aa + bb)(b + a)*a
3. aabb(a + b)*a
4. (bba*)* + (aab*a)* + ba
Answer: Option 1
Discussion
The b-loop at x2 can be written as b* and the a-loop at x4 as a*.
One path from start to final state (x1 to x3) is thus: aab*a.
The second path from start to final state (x1 to x4) is thus: bba*.
The ba-edge from x1 to x5 can be ignored as it does not lead to a final state.
It is now simply a matter of combining these parts of the regular expression to get
to aab*a + bba*
From this, it is clear that option 1 is the correct option.
The other options misinterpret the paths to final states, often incorrectly concatenating paths.
Question 2
Given FA1 (with regular expression r1) and FA2 (with regular expression r2), a transition table is being put
together to build an FA for r1 + r2.
New state Read an a Read an b
-z1 +z2 z3
+z2
Semester 1/2 2021
, Question 1
Kleene’s theorem can be used to turn a transition graph (TG) into a regular expression. Which one of the
following regular expressions would generate a language that would be equivalent to the language
described by the following TG?
1. aab*a + bba*
2. (aa + bb)(b + a)*a
3. aabb(a + b)*a
4. (bba*)* + (aab*a)* + ba
Answer: Option 1
Discussion
The b-loop at x2 can be written as b* and the a-loop at x4 as a*.
One path from start to final state (x1 to x3) is thus: aab*a.
The second path from start to final state (x1 to x4) is thus: bba*.
The ba-edge from x1 to x5 can be ignored as it does not lead to a final state.
It is now simply a matter of combining these parts of the regular expression to get
to aab*a + bba*
From this, it is clear that option 1 is the correct option.
The other options misinterpret the paths to final states, often incorrectly concatenating paths.
Question 2
Given FA1 (with regular expression r1) and FA2 (with regular expression r2), a transition table is being put
together to build an FA for r1 + r2.
New state Read an a Read an b
-z1 +z2 z3
+z2
