0

Can in set of possible final states reachable from initial state in nfa can consist of accepted state if input string is not a part of our given language? Here is the example, I want to discuss about-

Design a nfa for a language that accepts all strings over $\{a. b\}$ in which second last symbol is always '$a$'. One possible answer I know is here.(please scroll down to see the nfa)

Here can't we just get rid of $q2$ and have self loop on $q1$ with inputs $a,b$?(Edit-here I am taking $q1$ as accepted state.)

Prajwal Kansakar
  • 5,391
Aman Khandelwal
  • 3

1 Answers1

0

No you can't do that. If you do that, then the language of the NFA will contain the strings such as $a, ba, bba, \cdots$ which does not meet the criteria. In general, when you construct an automata that accepts a set of strings then the automata should accept those and only those set of strings, no more no less.

Prajwal Kansakar
  • 5,391
  • But in set of final states we have other states too, which are not accepted states. For eg- in a, ba, bba I can loop in q0 itself. In question I forgot to mention for 'another possible answer' I'm taking q1 as accepted state. Please see the question again. – Aman Khandelwal Nov 24 '17 at 07:28
  • An NFA will accept a string if there is at least one possible path from initial to the final state. So for example, in the NFA you suggested, for input $a$, one possible path is to loop in $q0$ itself as you say but another possibility is that the state changes from $q0$ to $q1$ which is an accepting state. So $a$ will be in the language of this NFA. – Prajwal Kansakar Nov 24 '17 at 07:38