Question

Identify the language accepted by the following NFA with $\in$-moves.

• All strings over a's and b's
• All strings which do not contain aa
• All strings which do not contain bb
• None of these

----------------------------------------------------------------------------------------------------

Made Easy Q 11, FLT 6- Practice Test 14

Here issue is that this language accepts (a+b)⁺

So my question is that ->

Do we include empty string in "All strings over a's and b's", to be honest I feel that answer given is incorrect, & IT should have been "All strings over a's and b's". Because empty string is not really a string which we should count over any alphabet. If they have said (a+b)* as first option , it was easy & Clear. But using words instead of precise notation , makes this question confusing. Please answer this question, what should be correct answer.

Comments

define Languages using set builder form to avoid ambiguity.

---

I know :) But we can't change the options in Exam !

---

Its not GATE question I guess. Hence, I avoid discussion over it.

---

Yeah you are right ! GATE questions will always use Set Builder notation (Based on Previous Experience! )

Answer 1

Above FA is accepting all strings over a and b excluding empty string so ans should be D.

[option A, all strings over {a, b}, means all strings starting from length 0, if something not explicitly given]

Comments

Yes all strings over sm alphabet always means including 0 len

Answer 2

I think option a is correct . because we can form any string of a & b which can be accepted by given NFA , but only epsilon is not accepted . string either end with a or b.

 

option B  and C looks incorrect , becoz there is loop with a and b . it means that it can take any number of a's and b's (aa & bb covered)

(a+b)+    is accepted    but (a+b)* is not accepted , because with epsilon we are not get into final state

Answer 3

Given answer is correct. It should be 'D', as empty string is not getting accepted.
All the strings over a and b implicitly includes the empty string i.e., {a+b}*