2 votes 2 votes 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. Theory of Computation theory-of-computation regular-language + – Akash Kanase asked Dec 1, 2015 • retagged Jun 4, 2017 by Arjun Akash Kanase 1.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply amarVashishth commented Dec 1, 2015 reply Follow Share define Languages using set builder form to avoid ambiguity. 1 votes 1 votes Akash Kanase commented Dec 1, 2015 reply Follow Share I know :) But we can't change the options in Exam ! 0 votes 0 votes amarVashishth commented Dec 1, 2015 reply Follow Share Its not GATE question I guess. Hence, I avoid discussion over it. 0 votes 0 votes Akash Kanase commented Dec 1, 2015 reply Follow Share Yeah you are right ! GATE questions will always use Set Builder notation (Based on Previous Experience! ) 1 votes 1 votes Please log in or register to add a comment.
Best answer 5 votes 5 votes 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] Pooja Palod answered Dec 1, 2015 • selected Dec 1, 2015 by Praveen Saini Pooja Palod comment Share Follow See 1 comment See all 1 1 comment reply Anurag_s commented Dec 1, 2015 reply Follow Share Yes all strings over sm alphabet always means including 0 len 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes 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 tiger answered Dec 1, 2015 tiger comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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}* monanshi answered Dec 1, 2015 monanshi comment Share Follow See all 0 reply Please log in or register to add a comment.