0 votes 0 votes Given L = { 0*1 + 0 + 1* + 10*1} where + symbol is UNION and NOT positive closure. Please draw the Minimal DFA for this. Theory of Computation finite-automata regular-expression regs theory-of-computation + – iarnav asked Mar 14, 2019 iarnav 874 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply ankitgupta.1729 commented Mar 14, 2019 i edited by ankitgupta.1729 Mar 15, 2019 reply Follow Share .... 2 votes 2 votes abhishekmehta4u commented Mar 14, 2019 reply Follow Share Starting state is also final state. 2 votes 2 votes iarnav commented Mar 15, 2019 reply Follow Share @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? 1 votes 1 votes iarnav commented Mar 15, 2019 reply Follow Share @ankitgupta.1729 Is there a simple way to draw DFA for this. I couldn't able to make it correct. 0 votes 0 votes ankitgupta.1729 commented Mar 15, 2019 reply Follow Share @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. 0 votes 0 votes iarnav commented Mar 15, 2019 reply Follow Share @ankitgupta.1729 Thank you for such a detailed explanation. May you please check my DFA, isme kya galti hai? 0 votes 0 votes ankitgupta.1729 commented Mar 15, 2019 reply Follow Share bhai, it will accept strings like 00,000,110,1100,1110,11001 which are not in the language. 1 votes 1 votes iarnav commented Mar 15, 2019 reply Follow Share Oh, right. Thank you! :) 1 votes 1 votes iarnav commented Mar 17, 2019 reply Follow Share @ankitgupta.1729. Bhai sorry to bother, but kya given language mein epsilon generate ho Raha hai? 0 votes 0 votes abhishekmehta4u commented Mar 17, 2019 reply Follow Share Yes bro, Language contain 1* = null, 1,11... 0 votes 0 votes ankitgupta.1729 commented Mar 17, 2019 reply Follow Share haan bhai.. 1* epsilon,1,11,111,..dega to sabhi ka union karne ke baad epsilon language me hoga.. 0 votes 0 votes iarnav commented Mar 17, 2019 reply Follow Share Thanks both of you, very much appreciated. 🙏 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes HI is this dfa fine>?? awanish.604 answered Mar 25, 2019 awanish.604 comment Share Follow See 1 comment See all 1 1 comment reply Verma Ashish commented Mar 26, 2019 reply Follow Share $\varepsilon$ should also be accepted.. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes https://drive.google.com/open?id=11ROM-L9EOewQutW-M4qiMmv7wd1pGtLl Spidey_guy answered Dec 31, 2019 Spidey_guy comment Share Follow See all 3 Comments See all 3 3 Comments reply newdreamz a1-z0 commented Dec 31, 2019 reply Follow Share 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* 1 votes 1 votes Spidey_guy commented Dec 31, 2019 reply Follow Share 00 is not generate by the regular expression,but the table you've given is accepting it. 0 votes 0 votes Spidey_guy commented Dec 31, 2019 reply Follow Share Thanks for pointing out the error. I think if we just add a transition of 1 from B to F , it will work fine. 0 votes 0 votes Please log in or register to add a comment.