CSI 3104 Introduction to Formal Languages Winter 2021
Answers to Mid-Term Question 1-11
1. TRUE (2 pt)
You can make ¡°ababacdb¡± by iterating star for 3 times: first time we choose ab, second we choose ab again, third we choose acdb.
2. FALSE (2 pt)
S*** will have the same members as S*
3. FALSE (2 pt)
4. Assume that L is non-regular and its complement is regular. This is contradiction since (L¡¯)¡¯ is
complement of regular language and so is regular. But (L¡¯)¡¯ = L. (2 pt)
5. TRUE (2 pt)
6. L is regular because it represents a finite language. A FA regarding this RE can simply have 21 states for ¡°a¡± and 20 states for ¡°b¡±. (2 pt)
7. FALSE (2 pt)
8. ¡°aba¡± is S*. One can produce ¡°aba¡± by either taking ¡°ab¡± first then ¡°a¡±, or by taking ¡°a¡± first
then ¡°ba¡±. Therefore, all words in S* do not have a unique factorization. (2 pt)
9. ( Total : 12 pt; each entry 1 pt) ab
-X1 X2 X3 X2 X4 X3 X3 X2 X4
+X4 X4 X4
10. (Total: 12 pt)
2 pt (each 0.5)
0.5 pt
1 pt
0.5 pt
4 pt ( each 0.5)
4 pt (each 0.25)
11. ( Total : 10 pt)
0.5 pt
0.5 pt
0.5 pt
0.5 pt
0.5 pt 0.5 pt
0.5 pt
0.5 pt
0.5 pt
0.5 pt
0.5 pt
0.5 pt 0.5 pt
0.5 pt 0.5 pt
0.5 pt
0.5 pt
0.5 pt 0.5 pt
0.5 pt