4 votes 4 votes Let $L$ be the language accepted by the following non-deterministic finite automaton with $\epsilon$-transitions: The number of states in the minimal DFA that accepts the language that is recognized by the above NFA over alphabet $\{a\},$ is ________ Theory of Computation goclasses2024-toc-1-weekly-quiz numerical-answers goclasses theory-of-computation finite-automata minimal-state-automata 2-marks + – GO Classes asked Jun 9, 2022 retagged Jun 17, 2023 by Lakshman Bhaiya GO Classes 503 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply faisal_sayyed commented Nov 15, 2022 i edited by faisal_sayyed Nov 16, 2022 reply Follow Share a→ q0q1q4q1q2q5q2q3q4q5*q3Deadq4q5*q5q4a→ q0q1q4q1q4q2q5*q2q5q3q4q5*q3q4q5q4q5*q4q5q4q5a→ ABBC*CD*DE*EE[AB][CDE][A] [B] [CDE]@Deepak Poonia sir, I am getting 3 states? Unable to understand where I am going wrong 🤔 0 votes 0 votes JAINchiNMay commented Nov 16, 2022 reply Follow Share @faisal_sayyed I have one query in first table from $q2$ on $a$ can we go to state $q5$ ? 0 votes 0 votes faisal_sayyed commented Nov 16, 2022 reply Follow Share Thanks, @JAINchiNMay. got it where I was going wrong. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes We can convert the given NFA into DFA and then minimize the resulting DFA. We’ll get the following minimized DFA. GO Classes answered Jun 9, 2022 edited Jun 9, 2022 by Lakshman Bhaiya GO Classes comment Share Follow See 1 comment See all 1 1 comment reply Hira Thakur commented Jun 17, 2023 reply Follow Share @GO Classes there is any algorithm that directly converts $\epsilon$ NFA to DFA? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Initial state: destination state @”a” q0 : q1q4 q1q4 : q2q5 q2q5 : q3q4 q3q4 : q5 q5 : q4 q4 : q5 Hence, total 6 states in minimal DFA. Udhay_Brahmi answered Jun 20, 2022 edited Nov 24, 2022 by Udhay_Brahmi Udhay_Brahmi comment Share Follow See all 4 Comments See all 4 4 Comments reply Sgm commented Jun 23, 2022 i edited by Sgm Jun 23, 2022 reply Follow Share @Udhay_Brahmi just wanted to confirm that will q2q5 on ‘a’ goes to q3q4 or it will go to q3q5q4 ? because as in the question, state q2 on ‘a’ goes only on q3 and q4 whereas it goes to q5 only on using ‘epsilon’ . 0 votes 0 votes yashforreal commented Nov 24, 2022 reply Follow Share q2 does not require “a” to go to q5, that is what is meant by “epsilon” transition. 0 votes 0 votes yashforreal commented Nov 24, 2022 reply Follow Share @Udhay_Brahmi q2q5 on transition over a won't go to q3q4q5, it will only go to q3q4 because q2 won't give q5 on transition over a because it can go to q5 with ε itself. 0 votes 0 votes Udhay_Brahmi commented Nov 24, 2022 reply Follow Share Thanks for pointing out @Sgm, @yashforreal. 👍👍Corrected now. 1 votes 1 votes Please log in or register to add a comment.