#TOC What will be the minimal DFA of this regular language?

Question

Given L = { 0*1 + 0 + 1* + 10*1}

where + symbol is UNION and NOT positive closure.

Please draw the Minimal DFA for this.

Comments

....

---

Starting  state is also final state.

---

@ankitgupta.1729 

Hi Bhai, nice to see you after so much time. I hope you're doing good.

Anyways, in the DFA you made, did you take all the languages individually and then made DFA for each of them and then club the DFAs because of the UNION?

or pehle baar mein he poora ek DFA bna diya aapne?

 

@abhishekmehta4u

Thanks bhai. Yes, b/c of epsilon initial = final state, right?

---

@ankitgupta.1729

Is there a simple way to draw DFA for this. I couldn't able to make it correct.

---

@abhishekmehta4u , Thanks bhai. edited.

@iarnav bhai, I have not made it by taking union of individual DFAs but I think right procedure is to make DFAs for individual component of this regular expression and then union of them and then minimize it.

First, I have written language as L={0,1,11,111,1111,...1*.........,01,001,0001,.....0*1,......101,1001,10001,.....10*1}

Then I observed the pattern of the strings, here 1* is one type of strings , 0*1 is another type of strings and by appending initially 1 in it then I got another type of strings 10*1 and one single 0....

Now I thought how to make DFA for it. So, I have to accept one string 0 first. So I made it by 2 states. Now, for 1* , I made it by accepting 11 first then by making loop of 1 on it. if I accept 1 initially and then make loop of 1 on it then there will be a problem for 10*1...Now I accepted 001 first and make a loop of 0 in middle. So I accepted 00*1 first. If I accept 01 first then there will be a problem for 0*1. So, I accepted 01 later. Since, I have already accepted 0*1 then I had no problem to append initially 1 by some state transition.

It takes some time to think and needs practice but take less time by making individual DFAs and then union of them. I also made it after 2-3 wrong attempts and I missed epsilon in language and made wrong DFA.  

---

@ankitgupta.1729

 

Thank you for such a detailed explanation.

May you please check my DFA, isme kya galti hai?

---

bhai, it will accept strings like 00,000,110,1100,1110,11001 which are not in the language.

---

Oh, right. Thank you! :)

---

@ankitgupta.1729.   Bhai sorry to bother, but kya given language mein epsilon generate ho Raha hai? 

---

Yes bro,
Language contain 1* = null, 1,11...

---

haan bhai.. 1* epsilon,1,11,111,..dega to sabhi ka union  karne ke baad epsilon language me hoga..

---

Thanks both of you, very much appreciated. 🙏

Answer 1

HI is this dfa fine>??

Comments

$\varepsilon$  should also be accepted..

Answer 2

https://drive.google.com/open?id=11ROM-L9EOewQutW-M4qiMmv7wd1pGtLl

Comments

01 is rejected in your dfa.

6 states is what i am getting.correct me if i am wrong.

D is dead state A is starting state ,states with(*) are final states.

	0	1
->A*	B*	E*
B*	B*	C*
C*	D	D
E*	B*	F*
F*	D	F*

 

---

00 is not generate by the regular expression,but the table you've given is accepting it.

---

Thanks for pointing out the error. I think if we just add a transition of 1 from B to F , it will work fine.