Solved

regular expression to DFA

Posted on 2008-09-30
8
460 Views
Last Modified: 2011-10-19
How do you draw this in a DFA?

w | each 1 in w is immediately preceded and immediately followed by a 0
0
Comment
Question by:kuntilanak
  • 5
  • 2
8 Comments
 
LVL 1

Accepted Solution

by:
yans earned 500 total points
Comment Utility
0
 

Author Comment

by:kuntilanak
Comment Utility
how does :

 b* + b*a(ba)*

satisfies my question, please explain
0
 
LVL 1

Expert Comment

by:yans
Comment Utility
The question deals with regular expression. b* + b*a(ba)* is a regular expression representation and the solution demostrates how to draw it.

If you may check some reference on reading regular expression syntax.

http://en.wikipedia.org/wiki/Regular_expression
0
 

Author Comment

by:kuntilanak
Comment Utility
I don't understand how b* + b*a(ba)* represents each 1 in w is immediately preceded and immediately followed by a 0
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:kuntilanak
Comment Utility
if 1 is equal to b here, then one possibility that regex gives me is 1* which can be an empty string and it is not followed immediately by a 0.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
0* (0 1 0 0*)*
0
 

Author Comment

by:kuntilanak
Comment Utility
ozo can you please explain that a bit
0
 

Author Comment

by:kuntilanak
Comment Utility

on the picture below, the start state is when given an input b, what if the input at the start state is a? It doesn't covers that..
dfa.png
0

Featured Post

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

by Batuhan Cetin Regular expression is a language that we use to edit a string or retrieve sub-strings that meets specific rules from a text. A regular expression can be applied to a set of string variables. There are many RegEx engines for u…
I have been reconstructing a PHP-based application that has grown into a full blown interface system over the last ten years by a developer that has now gone into business for himself building websites. I am not incredibly fond of writing PHP code o…
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now