The Gateway to Computer Science Excellence
+1 vote
1.2k 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 by (23 points)
edited by | 1.2k 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.
by Veteran (60.8k points)
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
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
198,047 comments
104,672 users