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

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.