Register

Regular Expressions - Is this solution correct?

1,292 views
1 1 vote

Q. Consider following Regular Expression:
(i) a*b*b (a+ (ab)*)* b*
(ii) a*(ab + ba)* b*
What is length of shortest string which is in both (i) & (ii)?
(a) 2
(c) 4
(b) 3
(d) None


Solution: Option (d)


Explanation:
The shortest string is ε generated by both the regular expressions

I believe the above explanation is wrong as (i) will generate at least 'b'.

Please correct me if I'm wrong.

1 Answer

2 2 votes

@Akash Mishra...i think u r right....

Q. What is length of shortest string which is in both (i) & (ii)? ....

:_) for the first RE....smallest string is  'b' which is also present in second RE....

hence ...answer i.e (length of smallest string present in both should be '1' ....which is not in the option hence 

option D

Voting & Accepting an answer helps improve the community
← Previous · #peterlinzNext → · Divide and Conquer
← Previous in category · #peterlinzNext in category → · Theory Of Computatio...
Position:
Show:

Related questions

0 0 votes
3 answers 3 answers
493
493 views
Snehasis_Basu asked Nov 10, 2024
493 views
Regular Expressions (doubt)
0 0 votes
1 1 answer
1.3k
1.3k views
M_Umair_Khan42900 asked Dec 29, 2022
1,253 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b]. s(a) p(pp)*( A + p)q + q and p*q (b) A +0(0+1)* + (0+1)* 00(0+1)* and ((1*0)*01*)* (c) (s*ttt)*s* and s*(ttts*)*
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)...
0 0 votes
1 1 answer
1.4k
1.4k views
Abhipsa asked Jan 21, 2019
1,434 views
Regular Expressions
Why this is not equal?(r+s)*=r*+s*