search
Log In
1 vote
1.7k views

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 B. 3 C. 4 D. None

in Theory of Computation
edited by
1.7k views
1
ans is none of these since min length is "b" present in both.

2 Answers

7 votes
 
Best answer
(i) a*b*b (a+ (ab)*)* b* = a*b*b (a+ ab)* b*

(ii) a*(ab + ba)* b*

Shortest string will be "b" only..

Length will be 1.

Option D.

selected by
0
For (ii) shortest can be epsilon as there is kleene star for every symbol.
1 vote
b is the smallest string derived by both languages.

hence answer is  min length =1

Option D

Related questions

1 vote
1 answer
1
318 views
Consider the following regular expression R=(a+b)* (a+b+ε)a which of the following is equivalent to the above a)(a*+b*)+ (aa+ba) b)(ε+a+b*)+ a c)(a+b)+ (a+b+ε)a d)None of these
asked Sep 15, 2018 in Theory of Computation Kshitij Hansda 318 views
2 votes
3 answers
3
2k views
Consider the following SDT. A → BC * (I) B.i = f(A.i)         (II) B.i = f(A.S)            (III) A.S = f(B.S) which of the above is violating L – attributed definition? (a) I only (b) II only (c) I, II (d) I, II, III
asked Sep 7, 2015 in Compiler Design ari 2k views
3 votes
1 answer
4
891 views
R= a*b* + b*a* How many final states exist in the minimized DFA that accepts a language equivalent to R. How many equivalence classes of ∑* to represent a language which is equivalent to R.
asked Jul 23, 2016 in Theory of Computation One 891 views
...