36 votes 36 votes Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $ Theory of Computation gatecse-2001 theory-of-computation easy descriptive finite-automata normal + – Kathleen asked Sep 14, 2014 edited May 15, 2018 by Milicevic3306 Kathleen 5.3k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Saurav Vinod commented Jun 3, 2018 reply Follow Share what if the remaining input will stand or loop within the state....................ie instead of giving b as back input let its loop there itself...............and same do for all???????? 1 votes 1 votes ankit3009 commented Nov 16, 2021 reply Follow Share I am saying for B = 1] Make DFA for odd number of A and another for odd number for B. 2] Then perform union and combine both the DFA’s. This way it would be more likely to be error less. 0 votes 0 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes DFA for A: Part (B): jayendra answered Jan 2, 2015 edited May 3, 2019 by Pooja Khatri jayendra comment Share Follow See all 2 Comments See all 2 2 Comments reply vupadhayayx86 commented Aug 28, 2018 reply Follow Share How dfa A will accept baabbaab?? I think there should be transition from final stage to state 2??? 0 votes 0 votes HeadShot commented Sep 2, 2018 reply Follow Share @vupadhayayx86 Observe, after "baab" , there is a loop (a+b)*, so after once "baab" occurred, it will accept anything. so yout string "baabbaab" will definitely be accepted. 1 votes 1 votes Please log in or register to add a comment.
16 votes 16 votes DFA for (B) Akash Kanase answered Nov 22, 2015 edited Nov 22, 2015 by Akash Kanase Akash Kanase comment Share Follow See all 4 Comments See all 4 4 Comments reply Praveen Saini commented Nov 22, 2015 reply Follow Share q3 will be final. q1 is for odd no of a's and even no of b's as it accepting a, bba, etc. 1 votes 1 votes Akash Kanase commented Nov 22, 2015 reply Follow Share Updated. 0 votes 0 votes Vaishnavi Gadhe commented Aug 23, 2022 reply Follow Share How this is possible they have given in question odd noo of a's and b's but according to this diagram it should be form even no. Of a's and b's 0 votes 0 votes Pranavpurkar commented Oct 29, 2022 reply Follow Share Vaishnavi Gadhe only odd are accepted. 0 votes 0 votes Please log in or register to add a comment.