Question

3" (25%) Give regular expressions for the following languages on {a, b). (a) L,-(a"b": n 4, m 3) (b) The complement of Li. (c) L- (w: w mod 3 03. Note: lw: the length of w (d) L3 w: |w mod 30 naww) appear)

Answer 1

3.

a) L1 = {aⁿb^m: n>= 4, m<= 3}

So we can have a's as among these {aaaa, aaaaa, aaaaaa, .... ...}

and b's as {$\epsilon$,b, bb, bbb}

the DFA for L1 will be

9l q8 a.b

hence the regular expression will be - aaaa(a*)($\epsilon$+b + bb + bbb)

b) As the complement of the above DFA will be

  

q0 02 94 g6 a,b

So the regular expression will be -

($\epsilon$ + a + aa + aaa)($\epsilon$ + b(a + b)*) + aaaaa*(b + bb )a(a + b)* + aaaaa*bbb(a + b)(a + b)*

c) L2 = {w : |w| mod 3 $\neq$ 0}

|w| mod 3 can be either 0,1, or 2

for |w| mod not equal to 0, |w| can be 1,2,4,5,7,8,10,11,...

The dfa will be

a,b q2

hence the RE will be : (a+b)+((a+b)(a+b))+((a+b)(a+b)(a+b)(a+b))*+((a+b)(a+b)(a+b)(a+b)(a+b))*

d) here the dfa will be :

26 a,b 911 аљ q2 2b

hence the RE : ((a+b)(a+b)(a+b))*

e)

The nfa for this language would be

q3 91 q2 94

hence the RE is:

aa(bb)*+bb(aa)*