?
Solved

regular expression to DFA

Posted on 2008-09-30
8
Medium Priority
?
467 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
8 Comments
 
LVL 1

Accepted Solution

by:
yans earned 2000 total points
ID: 22610815
0
 

Author Comment

by:kuntilanak
ID: 22610840
how does :

 b* + b*a(ba)*

satisfies my question, please explain
0
 
LVL 1

Expert Comment

by:yans
ID: 22610882
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:kuntilanak
ID: 22610905
I don't understand how b* + b*a(ba)* represents each 1 in w is immediately preceded and immediately followed by a 0
0
 

Author Comment

by:kuntilanak
ID: 22610911
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
ID: 22611143
0* (0 1 0 0*)*
0
 

Author Comment

by:kuntilanak
ID: 22611151
ozo can you please explain that a bit
0
 

Author Comment

by:kuntilanak
ID: 22616778

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

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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…
Do you hate spam? I do, and I am willing to bet you do as well. I often wonder, though, "if people hate spam so much, why do they still post their email addresses on the web?" I'm not talking about a plain-text posting here. I am referring to the fa…
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…
Suggested Courses
Course of the Month10 days, 14 hours left to enroll

770 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