theoryregular-languageautomatadfacomputation-theory

What will be the DFA for the regular expression 0(0+1)*0+1(0+1)*1?

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.

Solution

  • 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.