CS402 Assignment No 01 Fall 2019 Idea Solution

CS402 Assignment No 01 Fall 2019 Idea Solution

Q1. Show that the following pairs of regular expressions define the same language over the alphabet

L = {a, b}.

(i) (ab)*a         and    a(ba)*

(ii) (a* + b)*    and    (a + b)*

(iii) (a* + b*)* and    (a + b)*

                                                                                                                                     [9 marks = 3*3]

Q2. Develop a regular expression for the following language over the alphabet P = {a, b} such that it accepts all strings in which the letter b is never tripled. This means that no word contains the substring bbb.                                                                                                                                          [5 marks]

Q3. Develop a regular expression for the following language over the alphabet P = {a, b} such that it accepts all strings all words in which a is tripled or b is tripled, but not both. This means each word contains the substring aaa or the substring bbb but not both.                                                 [ 6 marks]