46 votes 46 votes The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$. Theory of Computation gatecse-2009 theory-of-computation finite-automata easy + – Kathleen asked Sep 22, 2014 edited May 1, 2019 by Pooja Khatri Kathleen 21.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 61 votes 61 votes Begin either with $0$ or $1$ Regular expression $:(0+1)(0+1)^*$ End with $0$ Regular expression $: (0+1)^*0$ End with $00$ Regular expression $:(0+1)^*00$ Containing the substring $00$ Regular expression $: (0+1)^*00(0+1)^*$ So, C is the correct answer. Praveen Saini answered Mar 6, 2015 edited Jan 11, 2023 by shadymademe Praveen Saini comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Pranavpurkar commented Oct 16, 2022 reply Follow Share Abhrajyoti00 Yes , brother. I think i was getting more than one option here that’s why confirmed using Arden’s theorem. 1 votes 1 votes JAINchiNMay commented Nov 16, 2022 reply Follow Share For option A,B take string 0 For option D take string 001 2 votes 2 votes PreyumKr commented Jan 7 reply Follow Share @JAINchiNMay great by proving with examples. cleared my doubts in seconds. 0 votes 0 votes Please log in or register to add a comment.
22 votes 22 votes 1. begin either with 0 or 1 contain '0' and '1' which is not accepted so false 2. end with 0 contain '110' which is not accepted.so false 3. end with 00 contain True here 4. contain the substring 00. contain 00101 which is not accepted i.e. take any string conatin the substring 00 and end with 1. so false so c is answer Prashant. answered Aug 6, 2016 Prashant. comment Share Follow See 1 comment See all 1 1 comment reply Ajitgate21 commented Sep 28, 2023 reply Follow Share Amazing Solution. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes I'll prove it by taking 'false string' A: Begin with '0' or '1' False String: 11,111,etc. B: End with '0' False String: 10,110,etc. D: Contain substring '00': 1001,10001,etc. So remaining option is C smartmeet answered Jan 13, 2017 smartmeet comment Share Follow See 1 comment See all 1 1 comment reply flash12 commented Jan 10, 2018 reply Follow Share 10 also end with '0' End with '0' False String: 10,110,etc. 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes I go with C. It contains all the strings which end up with 00. Gate Keeda answered Sep 23, 2014 edited Oct 1, 2014 by Gate Keeda Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.