1. (a) bbaa (2.5 pt) (b) bababb (2.5 pt)
4. (a) (2.5 pt)
a
(b) (2.5 pt)
a
b
+
CSI 3104 Introduction to Formal Languages Winter 2021
Answers to Assignment 2
2. (a) ( ¦« + a)(b + ba)* + (ab + b)*a* (3.5 pt)
(b) a(a+b+c)*(b+c) + b(a+b+c)*(a+c) + c(a+b+c)*(a+b) (1.5 pt)
3. (a) all the strings that end in ¡°baaaa¡± or ¡°b¡± (1.5 pt)
(b) all words that start with zero or many numbers of ¡°b¡±, following zero or many groups of odd numbers of consecutive ¡°a¡±s and ¡°b¡±s, following zero or many numbers of ¡°a¡±s. (3.5 pt)
ba baba
a -a
b a
bb a
b
b
b
a
b
a
b + a, b aa
b
5. (a). (a+b)((a+b)(a+b))*a (1.5 pt)
All the strings that have even length (2,4,…) and end in ¡°a¡± (1 pt) (b). (a + b ) a ((a + b ) a)* (1.5 pt)
All words of even length (non-zero) that don¡¯t have ¡°bb¡± and end with letter ¡®a ¡® (1 pt) Empty String : ¦«