Peter Linz Edition 4 Exercise 2.1 Question 6 (Page No. 47)

Question

With $Σ =  \{a,b\},$ give a DFA for $L = \{w_1aw_2: |w_1|\geq 3, |w_2|\leq 5\}.$

Answer 1

 L= w1aw2: |w1|≥ 3, |w2|≤ 5.

Here final states are -> q4 , q5, q6 , q7 , q8 , q9

[Edit]- By mistake, I have written q4 in two states. Actually, I should have start with q0 but started with q1. So understand the concept.  :)

Thanks, @Sourav Basu   :)

Comments

bro it is also accepting bbbabababa where w1=bbb and w2=bababa {|w2|>5}
but at same time if we assume w1=bbbab and w2=baba then there is no problem can u plzz tell me how this machine will differentiate for a that is between w1 and w2.??
thnx.... 

---

yes, you got it right ..

for L = bbbabababa

w1 = bbbab , w2 = baba

or you can assume,

w1 = bbbabab  , w2 = ba

or

w1 = bbbababab , w2 = epsilon.

 

Here, the key conccept is, language should not end with more than 5 consecutive b's after any a's and it must be satisfing  condition for W1. ( min length of 3 before that any a's ).

Hope you get the point..

---

ok ... thnx for rply bt i have a doubt as u r saying that 
" it must be satisfing  condition for W1. ( min length of 3 before that any a's )."
suppose string is bbaa so according 2 ur logic " it must be satisfing  condition for W1. ( min length of 3 before that any a's )." 
here w1=bb ie a string of length 2 before than first a . And this string also accepted by dfa. ie voilating the condition.
and if u take w1 as bba then it is right but then it is denying ur comment (" it must be satisfing  condition for W1. ( min length of 3 before that any a's )."). 

---

Brother, see what I said is - 

Here, the key conccept is, language should not end with more than 5 consecutive b's after any a's and it must be satisfing  condition for W1. ( min length of 3 before that any a's )..

I wanted to say about this any a's, ( not any a's ) ..  

After any first three (a + b) , now after getting "a" ...and now if any string ends with more than 5 consecutive b's then those strings should not be accepted..

Either, I wrote it in inappropriate way or you read it wrong .. 

---

thnx @vijaycs

---

@vijaycs Please rename second q4 state. You have used q4 twice for two different states.

---

As per my understanding..

if we take a string : bbbabbbbbb

then dfa must reject this string and your dfa is not able to reject this string.

Answer 2

the above  given answer is almost correct  

the correct dfa is

as follows

|w2|<=5

Comments

I think the above answer i.e., DFA

needs some  modification to satisfy the requirements of the given question.

Example : abaabbbbbbbbbabab

This string should be accepted by the DFA because we can find

W1 = abaabbbbbbbbb and

W2 = bab

So the above string must be accepted by the DFA but it is not acceptable by the above DFA.

 

That's what I'm thinking please correct if I'm wrong.

Answer 3

yes you are right since L={w1aw2}  where  length of w1(  |w1|  )  >= 3    and   length of  w2(  |w2|  )  <= 5

so   in  this  dfa  1st condition  |w1| is followed  upto  state q3   it will accept all strings having  |w1|>=3  

    2nd  condition is |w2| <= 5  so  q4 is accepting state  since  |w2|  can be 0  also   q21,q22,q23,q24 are accepting states also

since |w2| canbe 1,2,3.4 respectively  but it is wrong at  state q5 since  it should also be accepting  since condition is |w2|<=5

means  |w2| can be 5  so  q5 also be accepting and also  there should be an extra state which will act as dead state  name it

q6.

dead state -  state telling dfa not to accept strings ending computation at this state.

q0,q1,q2,q3 arev also dead states

Comments

can u draw a dfa for it.

Answer 4

To construct the DFA here we first consider the corresponding REGULAR EXPRESSION which makes it easy to construct DFA .

The regular expression for the given question is :

(a+b)(a+b)(a+b)(a+b)*a(a+b+€)(a+b+€)(a+b+€)(a+b+€)(a+b+€)

Where , € is the epsilon

Now see  @vijaycs

answer it is really well clear now.