TOC SAMPLE PRACTICE

Question

Consider the language defined by the regular expression (a | b) * b+.

Which of the following regular expressions also define that language?
(i) (a*b+) | (b*b+)
(ii) (ab |bb)*b*
(iii) (a | b | ba)*b+
(a) i only (b) i & ii only
(c) iii only (d) All of these
Solution: Option (c)

 

Need explanation why not all? we can obtain only b by taking (a | b) null it also applies to a option then why not a?

Answer 1

Given lang is (a + b) * b+ = {all strings ending with b}

a) (a*b+) + (b*b+)

This doesn't generate abab.

b) (ab + bb)*b*

This generate epsilon which is not in given Lang.

c) (a + b +ba)*b+

This generate all strings , ignore "ba" for a while, it became same as given regular expression.

Comments

please i am not getting it how?

(a*b+)  if we take a 1 time then it will generate ab as b+ means 1 b

and second time also same a taking 1 time will generate ab

so abab won't it?

---

you can generate abab if the regular expression was (a*b+)*
 but in this there is no "*"  (a*b+)

---

 Pranav Madhani

(a*b+)  it represents (any no. of 'a' followed by at least one 'b') here no 'a's are allowed to come after 'b'

Answer 2

string baab would not be constructed through regular expression 1 and 2