3 votes 3 votes What is the language accepted by the following DFA $\Sigma=(0,1)? Set of strings starting with 0 and have odd number of switchings (from 0 to 1 or 1 to 0, for example, 101 has two switchings) or starting with a 1 and have even no. of switchings. Set of all strings starting with 0 and have even number of switchings ( from 0 to 1 or 1 to 0, for example, 101 has 2 switchings) or starting with a 1 and have odd numbers of switchings. Explanation It accepts set of binary strings either start with a 0 and have an even number of switchings from 0 to 1) start with a 1 and have an odd number of switchings i.e. it accepts strings like {0, 010, 01110, 01010, 10, 1110, 1111010,…..} Here for string 010, there are two switchings: from 0 to 1 (010) from 1 to 0 (010) for string 01110, there are two transition from 0 to 1 (01110) from 1 to 0 (01110) Note: we do not consider moving from 0 to 0 or 1 to 1 as a switching Set of strings ending with zero set of all strings starting and ending with zero 2nd option is true but what abut the 3rd option it is also Correct I Guess Theory of Computation theory-of-computation finite-automata easy + – bad_engineer asked Aug 21, 2016 edited Sep 21, 2016 by go_editor bad_engineer 1.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes How can third option be correct? A single 0 is accepted her 10 is accepted here and many more which are also not ending wih '00'. yes! your point is strings ending with 00 is accepted, but in a single fsm how can you determine whether it will accept 00 or 10 ? to third option to be true 0,10 should not be accepted ,only string ending with 00 should be accepted.. so it is not the answer Aboveallplayer answered Aug 21, 2016 Aboveallplayer comment Share Follow See all 3 Comments See all 3 3 Comments reply Brijesh commented Aug 23, 2016 reply Follow Share Can you please explain why "only string ending with 00 should be accepted.."? 0 votes 0 votes bad_engineer commented Aug 24, 2016 reply Follow Share Exactly There is no mention that only only ending with 00 should be accepted 0 votes 0 votes Pavan Kumar Munnam commented Aug 30, 2016 reply Follow Share C is also correct 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Yes Option 3/C is also coreect. Explaination: L={0,00,000,10,110,110,100010,.....} or (0+1)*0 is Regular expersion for the given automata. If someone is not agree please tell me the input for which the given RE or FA will not be accepted. Brijesh answered Aug 23, 2016 Brijesh comment Share Follow See 1 comment See all 1 1 comment reply Kaluti commented Oct 1, 2017 reply Follow Share yes 3rd option is correct 0 votes 0 votes Please log in or register to add a comment.