Theory of computation

Question

Design a DFA corresponding to regular expression 1*(10)*

Answer 1

the language accepted by the regular expression $1^*(10)^*$ is :$(\epsilon,1,11,111,1111,….10,1010,101010,….110,1110,111010,1111010… \infty)$

invalid strings are: $(0,00,000...01,010,0011..\infty)$

Comments

can anyone please explain this solution

---

Here in the regular expression we have to accept string of the form 1*( any number of 1s), refer q1 state transition, which can be followed by any number of 10,

but the string cannot end with 1 (as it has to end with occurrence of 10), therefore q3 is non final state and if 11 appears once after 10 then we have to transit to dead state(q4) as no matter what are the next characters we don't have to accept the string.

Same is the case if the string starts with 0, then we have to transit to Dead state(q4).

---

@Hira Thakur  @prajjwal_191 anyone please???

Can you accept the string 1100, 100, 1000 to the above DFA. I just want to know that Is it necessary there is a path in a dfa for every symbol?? because in the above dfa there is no path for 0 symbol after q2

---

@techexplore In DFA always for every state for every input symbol there is exactly one transition.In above finite state machine there must be one transition from state q2 to q4 on input symbol 0 to make it DFA for accepting given regular expression. if you do not make that transition then also it is accepting the given regular expression but then it is not DFA it is NFA. 

---

 techexplore thanks for pointing it out. DFA is a complete system in which is defined for each input at each state.

$1100,100..$ all are invalid strings. so it is not accepted by DFA.

there is a path from $q_2\xrightarrow{0} q_4$