retagged by
683 views
4 votes
4 votes

Consider the regular languages denoted by the following pairs of regular expressions:

  1. $(0 + 1)$*$ = 0$*$ + 1$*$ $
  2. $0(120)$*$12 = 01(201)$*$2$
  3. $(0$*$l $*$)$*$ = (0$*$1)$*$ $
  4. $(01 +0)$*$0 = 0(10 +0)$*$ $ 

Determine the truth of equality for each pair.

  1. $a-False, b-True, c-True, d-False$
  2. $a-True, b-False, c-False, d-True$
  3. $a-True, b-True, c-False, d-True$
  4. $a-False, b-True, c-False, d-True$
retagged by

1 Answer

Best answer
5 votes
5 votes
Answer is (D)
Explanation:

a) (0+1)* = 0*+1* (LHS is syring containing 0s and 1s while RHS is string containing either 0s or 1s but both both for eg 00100, 010,011, etc are anti-examples) False

b) 0(120)*12 = 01(201)*2  (You can pass any string) True

c) (0*1*)* = (0*1)*  

Here, LHS=Any string while RHS=Ends with 1 (you can's pass strings like 100,00,1100,etc. False

d) (01 +0)*0 = 0(10 +0)*  Both strings starts and Ends with '0' and NO 1's together(alternative 1's) True

So, answer is FTFT which is in option (D)

Correct me if I'm wrong!
selected by
Answer:

Related questions