1.
(5 pt)
CSI 3104 Introduction to Formal Languages Winter 2021
Answers to Assignment 4
1/1 0/0
0/#
1/#
0/#
1/#
0/# 1/#
2.
(5 pt)
3.
( Total : 12 pt)
a) The machine counts the number of “b”s occurring after the first letter. (5 pt)
0/6 1/7
000
q1/1 1 q2/0
1 q3/0
b) (5 pt)
q0/0 q1/0 q2/1
1
a
a,b ab b
c)0010 (1pt) d) 00010 (1 pt)
4. (Total : 11 pt)
𝐿1 ∩𝐿2 =(𝐿1 +𝐿2)′(1pt)
L1 : ((a+b)(a+b))* L’1 :
a, b
a, b
a, b
a, b
′′
+
1 pt
a, b
q0
q1 +
1 pt
a, b
– a
L2 : ((a+b)*aa(a+b)*)
L’2 :
L’1 + L’2 :
a +
1 pt
b
b
X0 +
a
b
X1 +
X2
a, b
a
1 pt
a, b
a, b
x0 q0 ++
a
a
x1 q1
x2 q0
x2 q1 +
b
b
b
2 pt
a
a
x0 q1 +
x1 q2 +
b
(L’1 + L’2)’ :
a, b
a, b
x0 q0
x0 q1
x1 q1 a
x1 q2
2 pt
x2 q0 +
a
x2 q1
a
b
b
b
2 pt
a
b
RE: ((a+b)(a+b))*aa((a+b)(a+b))*
5. ( Total : 17 pt)
By contradiction, assume that L is regular. Therefore, based on pumping lemma, there is a number p (the pumping length) where if s is any string in L of length at least p, then s may be divided into three pieces, s = xyz satisfying three conditions.
Assume that s = (a+b)pcp |s|≥ p (1 pt)
Therefore, s can be split into three pieces s = xyz where for any 𝑖 ≥ 0 the string 𝑥𝑦𝑖𝑧 is in L (1 pt). There are 3 cases:
a. y is in the first part (a+b)p (3 pt): in this case xyyz is not in L (1 pt). Because the number of “a”s or “b”s will be more than the number of “c”s (1).
b. y is in the second part (c)p (3 pt): same as above (1 pt). The number of “c”s will be more than the number of “a”s or “b”s (1 pt).
c. y is in both parts (3 pt): in this case, xyyz is not in L (1 pt). Because we would have repetition of “a”s (or “b”s) and “c”s in the middle of word with is not in the language. All “c”s must appear at the end of a word (1 pt).
Therefore, L is not regular.
Total points of the assignment : 50