8 votes 8 votes Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite. If $\text{D}$ accepts some string of length $n-1$, then the language of $\text{D}$ is infinite. If $\mathrm{N}$ accepts some string of length $n$, then the language of $\mathrm{N}$ is infinite. If $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite. Theory of Computation goclasses2024-mockgate-12 goclasses theory-of-computation finite-automata multiple-selects 2-marks + – GO Classes asked Jan 21 • retagged Jan 25 by Lakshman Bhaiya GO Classes 780 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply GO Classes Support commented Jan 25 reply Follow Share $ \large{\colorbox{yellow}{Detailed video solution of this question with direct time stamp}}$ All India Mock Test 3 - Solutions Part 1 0 votes 0 votes Rahulji commented Jan 30 i edited by Rahulji Jan 30 reply Follow Share great explanation 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes If the DFA has $n$ states, and the language contains any string of length $n-1$ or more, then the language is infinite. If the NFA has $n$ states, and the language contains any string of length $n$ or more, then the language is infinite. GO Classes answered Jan 21 • edited Jan 21 by Lakshman Bhaiya GO Classes comment Share Follow See all 5 Comments See all 5 5 Comments reply zoy123 commented Jan 22 reply Follow Share how B is correct ? 2 votes 2 votes equimanthorn commented Jan 22 reply Follow Share Its straightforward to accept a (n-1) length string with n states. But the issue is that since its a DFA, the last state should have transitions defined for it. Already we’ve exhausted our ‘n’ states so we can’t add anymore states. To define a transition for the final state, the only option is to have a transition to itself (self loop) OR to other states, causing a cycle. In both cases, we’d have a infinite language, since we can keep going round the loops/cycles to generate more and more, and thus, infinite strings, that the language can accept. You can try for n = 3 for example. 6 votes 6 votes jugnu1337 commented Jan 22 reply Follow Share @Sachin Mittal 1 how b is true. 1 votes 1 votes Shreyash007 commented Jan 23 reply Follow Share In n states and n-1 strings the language may be finite and may be infinite both cases are possible. But the option B says Language is always infinite which is Wrong. 1 votes 1 votes bluesta commented Feb 15 reply Follow Share see for DFA we need to have transition for each symbol... so try to make DFA for L={a+b}2We Need 3 + 1 (one final and one reject) states Now here n = 4 then n-1 = 3But our DFA can only accept 2 length string So according to option B our DFA is supposed to accept 3 length string therefore we need a Loop to accept n-1 length string. 0 votes 0 votes Please log in or register to add a comment.