Automata theory basic

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

Moderator: CS Moderators Team

Automata theory basic

Postby 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
Parakrant
 
Posts: 19
Joined: Wed Jan 04, 2012 8:50 am
My College/Company:: NEHU
Roll Number: 27121211

Re: Automata theory basic

Postby 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
Thanks,
Mallesham (M.Tech - IITBombay)
CSE
Gateforum HYD
malleshamd
Gatementor Newbie
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

Re: Automata theory basic

Postby 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
You do not have the required permissions to view the files attached to this post.
Thanks,
Mallesham (M.Tech - IITBombay)
CSE
Gateforum HYD
malleshamd
Gatementor Newbie
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

Re: Automata theory basic

Postby Parakrant » Sat Feb 04, 2012 12:13 pm

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

Re: Automata theory basic

Postby 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.
ashfaque87
 
Posts: 1
Joined: Sat Jun 20, 2015 5:59 pm
My College/Company:: Not Working
Roll Number: 0


Return to CS Question

Who is online

Users browsing this forum: No registered users and 6 guests
cron