COS2601/203/1/2017
Tutorial letter 203/1/2017
Theoretical Computer Science II
COS2601
Semester 1
School of Computing
Discussion of Assignment 3
BARCODE
, Dear student
Solutions to the questions of assignment 3 are provided in this tutorial letter.
Regards
COS2601 team
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
2
Tutorial letter 203/1/2017
Theoretical Computer Science II
COS2601
Semester 1
School of Computing
Discussion of Assignment 3
BARCODE
, Dear student
Solutions to the questions of assignment 3 are provided in this tutorial letter.
Regards
COS2601 team
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
2
