The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
43 views
Minimum states required for DFA that accepts :

L = {w1 x w2 | w,x belongs to {a,b}* | w1 >= 0, w2 > 1 and x >= 0 }.
asked in Theory of Computation by Loyal (6.6k points) | 43 views
0
3.
0
a*a*a+ = a+ i.e the form will be (a+b)^+

1 Answer

+3 votes
Best answer

we have,

L = {w1 x w2 | w,x belongs to {a,b}* | w1 >= 0, w2 > 1 and x >= 0 }.

means regular expression for L = (a+b)*  (a+b)* (a+b)2(a+b)*

                                                   =set of strings having length atleast 2.

so number of states in minimal DFA = 3 states.

 

answered by Boss (11.9k points)
selected by
0
Brother i can substitute w1 as epsilon w2 as say (a+b) and x as also epsilon. So according to it the minimum length string should be 1. What is wrong here ?
0
Yes so states would be 2.
0

@na46a the question says w2>1 means  size of w2>= 2symbols.

 

0
(a+b)^+ Yes you are correct.
0

@ad140 see the question once again it would be (a+b)2(a+b)*

0
Yes I didn't see >1 I saw it as >=1 so it will be >=2 so there will be three states. I had done a similar mistake in my sessionals too.
0
Ohk i got it so w2 i can take as (a+b)^2 so if i take minimum value of every Expression so w1 = epsilon , w2 is (a+b)^2 and x = epsilon so minimum string will be of length 2 or i could take w1 = (a+b)* , w2 = (a+b) and x as epsilon so L = (a+b)*(a+b)^2. Hence total 3 states am i right ?
0
Yes
0
@ad140 @na462 yes now u got that. :)
+1

@Na462

it's your responsibility, to select as BEST if you are satisfied with the answer

0
@shaikh :p

Related questions

+1 vote
1 answer
6
0 votes
1 answer
7
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
49,814 questions
54,518 answers
188,351 comments
75,296 users