2

This is the DFA i have drawn-

MyDFA

Is it correct?
I am confused because q4 state has 2 different transitions for same input symbol which violates the rule of DFA, but I can't think of any other solution.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Chris
  • 39
  • 1
  • 4
  • See also [this question](http://stackoverflow.com/questions/7550711/what-is-the-language-of-this-deterministic-finite-automata/13965717#13965717) . – Grijesh Chauhan Jan 03 '13 at 07:02
  • chirs view my updated answer I corrected DFA – Grijesh Chauhan Jan 27 '13 at 04:08
  • Determinicy refers to the fact that it is not allowed to have two outgoing transitions with the same label from the same state. It does **not** refer to incomming transitions. – Dan Jan 28 '13 at 18:50

2 Answers2

4

Your DFA is not correct.
your DFA is completely wrong so I don't comment

DFA for RE: 

0(1 + 0)*0 + 1(1 + 0)*1

Language Description: if string start with 0 it should end with 0 or if string start with 1 it should end with 1. hence two final states (state-5, state-4).

state-4 : accepts 1(1 + 0)*1
state-5 : accepts 0(1 + 0)*0
state-1 : start state.

DFA:

DFA

EDIT :

+ Operator in Regular Expression

(0 + 1)* = (1 + 0)* that is any string consist of 1s and 0s, including Null string ^.

Here + means Union if it appear between two RE: and A U B = B U A (similarly)=> (0 + 1) = (0 + 1) .

meaning of plus + depends on syntax it appears in: If expression is a+ (+ is superscripted) this means one of more as, and If a+b then + means Union operation either a or b.

a+ : { a, aa, aaa, aaa.....} that is any number of a string in language with length > 1.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • I believe it is 0(0+1)*0+1(0+1)*1 instead of 0(1 + 0)*0 + 1(1 + 0)*1 – Helio Santos Jan 02 '13 at 14:41
  • 2
    @HélioSantos Is there any difference? – Chris Jan 02 '13 at 15:10
  • yes, its a regular expression, not a math expression. (0+1) => one or more zeroes followed by a one (1+0) => one or more one followed by a zero – Helio Santos Jan 02 '13 at 15:15
  • 2
    @HélioSantos Yes it is a regular expression. I think (0+1)* means any number of zeroes and ones, same as (1+0)* . From your point, my regular expression doesnot accept 0010, but it does. – Chris Jan 02 '13 at 15:25
  • @Chris that would be [01]* any number of zeroes OR ones (01|10)* any number of the combination 01 OR 10. Try here(http://rubular.com/). Which regex implementation are you using? – Helio Santos Jan 02 '13 at 15:50
  • 1
    @HélioSantos `(0 + 1)*` means any string consist of `0`s and `1`s including `^` and `(O+1)* = (1+0)*`. Actually `+` means Union and `A U B` = `B U A`. – Grijesh Chauhan Jan 02 '13 at 17:03
  • @GrijeshChauhan `+` is a quantifier. The element before `+` should appear one or more times (http://www.regular-expressions.info/repeat.html). Are we talking about the same thing - regex?? – Helio Santos Jan 02 '13 at 18:27
  • @HélioSantos meaning of plus depends on syntax it appears if expression is `a+` this means one of more `a`s and if `a+b` then `+` means Union operation either `a` or `b`. – Grijesh Chauhan Jan 03 '13 at 04:41
  • @HélioSantos [**+ in Regular Expression**](http://www.jflap.org/tutorial/regular/index.html) – Grijesh Chauhan Jan 03 '13 at 10:33
  • @HélioSantos Welcome your! :) – Grijesh Chauhan Jan 03 '13 at 12:40
0

I think you should start with 0 first

0(1 + 0)*0 + 1(1 + 0)*1

enter image description here

lucascaro
  • 16,550
  • 4
  • 37
  • 47
Abdul Wali Khan Afridi
  • 41
  • 1
  • Welcome to [so]! Generally, answers are much more helpful if they include an explanation of what the code (or formula) is intended to do, and why that solves the problem without introducing others. – lucascaro Nov 08 '18 at 06:20