pl explain ur ans!

q1. Number of states in DFA accepting the following langauge is L={a^nb^2m:n,m>=1}

a.3

b.4

c.2

d.5

q2. Number of states in DFA accepting the string containing atmost 2a's and atmost 2b's over {a.b} is

a.10

b.9

c.8

d.11

Enter Name of Correspondence Set, Page Number, Question Number, Your Name and Roll Number for Query!

**Moderator:** CS Moderators Team

5 posts
• Page **1** of **1**

by **Parakrant** » Wed Feb 01, 2012 12:08 pm

pl explain ur ans!

q1. Number of states in DFA accepting the following langauge is L={a^nb^2m:n,m>=1}

a.3

b.4

c.2

d.5

q2. Number of states in DFA accepting the string containing atmost 2a's and atmost 2b's over {a.b} is

a.10

b.9

c.8

d.11

q1. Number of states in DFA accepting the following langauge is L={a^nb^2m:n,m>=1}

a.3

b.4

c.2

d.5

q2. Number of states in DFA accepting the string containing atmost 2a's and atmost 2b's over {a.b} is

a.10

b.9

c.8

d.11

- Parakrant
**Posts:**19**Joined:**Wed Jan 04, 2012 8:50 am**My College/Company::**NEHU**Roll Number:**27121211

by **malleshamd** » Sat Feb 04, 2012 3:26 am

1.Number of states in DFA accepting the following langauge is L={a^nb^2m:n,m>=1}

Solution:

Minimum length of string is: abb

q1 is initial state and q4 is final state.

-->(q1)---a--->(q2 with self loop for a)---b--->(q3 with self loop for b)---b--->((q4 with self loop for b))

From q1 with input b, transition goes to dead state(q5).

From q3 and q4 with input a, transition goes to dead state(q5).

Total number of states = 5

Solution:

Minimum length of string is: abb

q1 is initial state and q4 is final state.

-->(q1)---a--->(q2 with self loop for a)---b--->(q3 with self loop for b)---b--->((q4 with self loop for b))

From q1 with input b, transition goes to dead state(q5).

From q3 and q4 with input a, transition goes to dead state(q5).

Total number of states = 5

Thanks,

Mallesham (M.Tech - IITBombay)

CSE

Gateforum HYD

Mallesham (M.Tech - IITBombay)

CSE

Gateforum HYD

- malleshamd
- Gatementor Newbie
**Posts:**147**Joined:**Sat Feb 04, 2012 3:11 am**Currently what are you doing?:**Am Working**My College/Company::**Gateforum**Roll Number:**11111234**Packages:**Classroom Coaching (CL)**City:**Hyderabad

by **malleshamd** » Sat Feb 04, 2012 4:02 am

q2. Number of states in DFA accepting the string containing atmost 2a's and atmost 2b's over {a.b} is ?

Solution:

L={Epsilon,a,b,aa,ab,bb,ba,aab,aba,abb,bba,bab,baa,similarly four length string with atmost 2a's and 2b's}

Attached DFA image. Number of states = 10

Solution:

L={Epsilon,a,b,aa,ab,bb,ba,aab,aba,abb,bba,bab,baa,similarly four length string with atmost 2a's and 2b's}

Attached DFA image. Number of states = 10

You do not have the required permissions to view the files attached to this post.

Thanks,

Mallesham (M.Tech - IITBombay)

CSE

Gateforum HYD

Mallesham (M.Tech - IITBombay)

CSE

Gateforum HYD

- malleshamd
- Gatementor Newbie
**Posts:**147**Joined:**Sat Feb 04, 2012 3:11 am**Currently what are you doing?:**Am Working**My College/Company::**Gateforum**Roll Number:**11111234**Packages:**Classroom Coaching (CL)**City:**Hyderabad

- Parakrant
**Posts:**19**Joined:**Wed Jan 04, 2012 8:50 am**My College/Company::**NEHU**Roll Number:**27121211

by **ashfaque87** » Sat Jun 20, 2015 6:25 pm

for the question number 1 :

-->(q1)---a--->(q2 with self loop for a)---b--->(q3 with self loop for b)---b--->((q4 with self loop for b))

I do not think that the self loop in state q3 for b and the self loop in state q4 for b makes the appropriate DFA as it accepts any number of b's >2.

but we need the number of b's of even length >=2

-->(Q1)---a--->(Q2 with self loop for a)---b--->(Q3)---b--->(Q4 accepting state and a loop from Q4 to Q3 for b )

and from Q1 ,Q3 and Q4 the transitions over the missing alphabets go to a dead state Q5.

The number of states in the DFA = 5.

-->(q1)---a--->(q2 with self loop for a)---b--->(q3 with self loop for b)---b--->((q4 with self loop for b))

I do not think that the self loop in state q3 for b and the self loop in state q4 for b makes the appropriate DFA as it accepts any number of b's >2.

but we need the number of b's of even length >=2

-->(Q1)---a--->(Q2 with self loop for a)---b--->(Q3)---b--->(Q4 accepting state and a loop from Q4 to Q3 for b )

and from Q1 ,Q3 and Q4 the transitions over the missing alphabets go to a dead state Q5.

The number of states in the DFA = 5.

- ashfaque87
**Posts:**1**Joined:**Sat Jun 20, 2015 5:59 pm**My College/Company::**Not Working**Roll Number:**0

5 posts
• Page **1** of **1**

Users browsing this forum: No registered users and 4 guests

- The team • Delete all board cookies • All times are UTC + 5:30 hours

Powered by www.gateforum