The Gateway to Computer Science Excellence
+1 vote

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 by (23 points)
edited by | 1.2k views
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.
by Veteran (60.8k points)
selected by
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
by Boss (32.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
104,672 users