3 votes 3 votes In the DFA (not necessarily minimal) for a regular language $L$ over $\Sigma = \{a, b, c,d\},$ the minimum number of outgoing edges for any state is _____ Theory of Computation go2025-toc-1 numerical-answers regular-language + – gatecse asked Sep 29, 2020 gatecse 354 views answer comment Share Follow See 1 comment See all 1 1 comment reply nachi78 commented Dec 19, 2023 reply Follow Share My doubt was the question asked for ‘Outgoing Edges’ not ‘All edges’, so I thought in a DFA there should be just one ‘Incoming Edge’, and others outgoing. Thus 3 outgoing and 1 incoming. 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes In any DFA, a state should have a transition for all the symbols in the alphabet set. So, the correct answer is $4.$ gatecse answered Sep 29, 2020 • selected Sep 26, 2021 by Arjun gatecse comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments shashankrustagi commented Dec 22, 2020 reply Follow Share Correct Thanks sir 0 votes 0 votes deepz commented Jan 31, 2021 reply Follow Share Isn’t this the maximum number of outgoing edges as well? In a DFA, every state need to have a transition defined for all the input alphabets. So isn’t it the maximum and minimum as well? 0 votes 0 votes palashbehra5 commented Jan 2, 2022 reply Follow Share deepz yes. 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes why it’s not 1? i was also confused , so sir written in comments but wanna highlight this , so writing it again here……..so no one can miss this point!! only one edge contain all alphabet set {a,b,c,d} Then it automatically becomes 4 edges. It is for simplicity of drawing that only one line is shown. MANSI_SOMANI answered Oct 13, 2022 MANSI_SOMANI comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In DFA we should have transition from a state for all the symbols present in alphabet. So answer is 4. eshita1997 answered Oct 7, 2020 eshita1997 comment Share Follow See all 0 reply Please log in or register to add a comment.