GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43

Answer 1

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.

Comments

how B is correct ?

---

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.

---

@Sachin Mittal 1 how b is true.

---

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.

---

see for DFA we need to have transition for each symbol... so try to make DFA for 

L={a+b}²

We Need 

3 + 1 (one final and one reject) states 

Now here n = 4 

then n-1 = 3

But 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.