7 Replies - 6107 Views - Last Post: 29 January 2010 - 11:48 PM

#1 mrsenim  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 28-January 10

Is this valid transition diagram for DFA?

Post icon  Posted 28 January 2010 - 07:57 AM

Hello,

I am confused if this is a valid transition diagram of equivalent DFA to a NFA supporting the language described by the Regular Expression
 (a+b)*bb(a+b)* 
in following file.

http://mathforum.org...585173/file.bmp

If it is correct then is it possible to make a DFA without showing the out-going transition of a on initial state 1.

Please also see the diagram in following file.

http://mathforum.org...5174/second.bmp

Pleasy Reply

Thanks!

Is This A Good Question/Topic? 0
  • +

Replies To: Is this valid transition diagram for DFA?

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Is this valid transition diagram for DFA?

Posted 28 January 2010 - 10:49 AM

alright so the regular expression describes the set of strings that contain substring "bb"..the NFA diagram is correct(you have to indicate the start and accept states though), but the DFA one is not, why??..because a DFA must not contain any epsilon transitions, and every state must have one and only one transition arrow for each symbol in the alphabet going out of it to some other state.. in the DFA diagram that is on the link, there is no transition arrow carrying symbol 'a' out of state 1 which doesnt make it a valid DFA.. because if the automata is at state 1 and it sees an 'a' on its input tape, it wont know what to do and it will crash..that shouldn't happen with a DFA, since DFA's are deterministic as their names imply, they should always know what to do when they read any symbol during the computation

This post has been edited by mostyfriedman: 28 January 2010 - 10:55 AM

Was This Post Helpful? 0
  • +
  • -

#3 mrsenim  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 28-January 10

Re: Is this valid transition diagram for DFA?

Posted 28 January 2010 - 11:54 PM

Thank You mostyfriedman. Actually this was what (in my first post) was published in the book I am reading on automata. But another place the DFA shows correct diagram for this language i.e,
 (a+b)*bb(a+b)* 
. This was the reason that I was confused. It seems some printing mistake. Anyways

Another problem I am confronting is that

Consider a language

 L = {NULL, b, ab, bb} 


defined over

 SIGMA={a,b} 


expressed by the regular expression

 NULL+b(NULL+a+b) 


So should the regular expression not be

 NULL+(NULL+a+b)b 


To represent the language L correctly?

or while expressing RE there's no difference in
 NULL+b(NULL+a+b) 


and in

 NULL+(NULL+a+b)b 


Please help.

Thanks again.
Was This Post Helpful? 0
  • +
  • -

#4 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Is this valid transition diagram for DFA?

Posted 29 January 2010 - 10:01 AM

i'm sorry but i dont really get the question...are you asking, what should be the regular expression for the language L?
Was This Post Helpful? 0
  • +
  • -

#5 suresh.chereddy@gmail.com  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 57
  • Joined: 06-February 08

Re: Is this valid transition diagram for DFA?

Posted 29 January 2010 - 10:14 AM

thak you..i heve also learnt this from discussion...thank you dudes
Was This Post Helpful? 0
  • +
  • -

#6 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Is this valid transition diagram for DFA?

Posted 29 January 2010 - 12:19 PM

if you are asking which should be the correct regular expression for this language then
(NULL+(NULL+a+b)b)
is the correct one..

NULL+b(NULL+a+b)
is incorrect because you can only derive the empty string or strings that start with a 'b'..you will not be able to derive any string that starts with an 'a' such as "ab" and that string belongs to L..so this regular expression doesn't describe the language L..

hope this helps

This post has been edited by mostyfriedman: 29 January 2010 - 12:22 PM

Was This Post Helpful? 1
  • +
  • -

#7 mrsenim  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 28-January 10

Re: Is this valid transition diagram for DFA?

Posted 29 January 2010 - 11:39 PM

View Postmostyfriedman, on 29 Jan, 2010 - 11:19 AM, said:

if you are asking which should be the correct regular expression for this language then

hope this helps


Sure, thank you.

This post has been edited by mrsenim: 29 January 2010 - 11:51 PM

Was This Post Helpful? 0
  • +
  • -

#8 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Is this valid transition diagram for DFA?

Posted 29 January 2010 - 11:48 PM

no problem..glad i could help..if you have any more questions then don't hesitate to post them here :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1