1 votes 1 votes 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 Theory of Computation theory-of-computation + – gate chintu asked Jun 16, 2015 edited Jul 23, 2016 by LeenSharma gate chintu 9.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply Prashant. commented Jul 21, 2016 reply Follow Share ans is none of these since min length is "b" present in both. 1 votes 1 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes (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. Digvijay Pandey answered Jun 16, 2015 selected Jul 23, 2016 by LeenSharma Digvijay Pandey comment Share Follow See 1 comment See all 1 1 comment reply AnilGoudar commented Jun 18, 2017 reply Follow Share For (ii) shortest can be epsilon as there is kleene star for every symbol. 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes b is the smallest string derived by both languages. hence answer is min length =1 Option D sh!va answered Jul 21, 2016 sh!va comment Share Follow See all 0 reply Please log in or register to add a comment.