27 votes 27 votes Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the substring $00$ nor the substring $11$. Consider the grammar $S \to aSAb $ $S \to \epsilon $ $A \to bA $ $ A \to \epsilon $ where $S$, $A$ are non-terminal symbols with $S$ being the start symbol; $a, b$ are terminal symbols and $\epsilon$ is the empty string. This grammar generates strings of the form $a^ib^j$ for some $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$? Theory of Computation gatecse-2000 theory-of-computation descriptive regular-language context-free-language + – Kathleen asked Sep 14, 2014 edited May 15, 2018 by Milicevic3306 Kathleen 4.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 40 votes 40 votes Language $L = (0+1)^*- (0+1)^*(00+11) (0+1)^*$ $\textsf{DFA}$ contains $4$ states of which $3$ are final and $1$ is dead state. $i \leq j$ as $S \rightarrow aSAb$ There will be always one $a$ in left and minimum one $b$ in right and $A \rightarrow bA \mid \epsilon$ can generate any number of $b\text{’}$s including null string. If $A$ is $\epsilon$ then $i=j$ and if $A$ is generating any $b,$ then $j>i$ so condition is $i\leq j.$ Mithlesh Upadhyay answered Apr 23, 2015 edited May 31, 2021 by Arjun Mithlesh Upadhyay comment Share Follow See all 16 Comments See all 16 16 Comments reply rameshverma1999 commented May 3, 2015 reply Follow Share in answer a why three final state mark it should be one final state as in question it has sub string 00 ot 11 plese explain 0 votes 0 votes rohith1001 commented Sep 8, 2019 reply Follow Share For 13b) The grammar never generates all strings with just b*. For b* we have i=0 and j>=0. But these strings are not generated. Hence the condition needs to be j>=i for all i>0 j=i for i=0 1 votes 1 votes ayushsomani commented Dec 6, 2019 reply Follow Share @Satbir @rohith1001 They have asked for Minimal Finite Automata $\Rightarrow$ We can have a minimal NFA (instead of DFA). How to draw NFA for such problems? 1 votes 1 votes rohith1001 commented Dec 6, 2019 reply Follow Share @ayushsomani Refer these two images. Page1: https://gateoverflow.in/?qa=blob&qa_blobid=13292319058827833562 Page2: https://gateoverflow.in/?qa=blob&qa_blobid=2858136095014749190 0 votes 0 votes rohith1001 commented Dec 6, 2019 i edited by rohith1001 Dec 6, 2019 reply Follow Share @ayushsomani As explained in the solution we can draw a DFA that contains either 00 or 11 as substring and then take its complement. This is the best recommended solution. or We can draw seperate DFA's and then take intersection. But this is time consuming. :( 0 votes 0 votes ayushsomani commented Dec 6, 2019 reply Follow Share @rohith1001 So, if it is asked Minimal Finite Automata, then i can draw a minimal DFA coz minimal DFA == minimal NFA? 0 votes 0 votes rohith1001 commented Dec 6, 2019 i edited by rohith1001 Dec 6, 2019 reply Follow Share No. If they ask minimal finite automata, we will have to draw NFA only. Note: (number of states in minimal NFA) <= (number of states in minimal DFA) For this question, you can just remove the trap state to get the minimal NFA. 0 votes 0 votes ayushsomani commented Dec 6, 2019 reply Follow Share @rohith1001 But, removing Dead states (if any) from minimal DFA can't assure a minimal NFA, coz It's not necessary that we have all transitions in NFA. 0 votes 0 votes rohith1001 commented Dec 6, 2019 reply Follow Share I think you are right. For this question removing the dead state gives us the minimal NFA. 0 votes 0 votes ayushsomani commented Dec 6, 2019 reply Follow Share @rohith1001 Bro, while we take Cross product of two DFA's having m and n states respectively, then we say that the resulting DFA should contain m*n States? 0 votes 0 votes rohith1001 commented Dec 6, 2019 reply Follow Share Yes. The cross product has m $\times$ n states, but it need not be a minimum DFA. Hence we will have to minimize it. 0 votes 0 votes ayushsomani commented Dec 6, 2019 reply Follow Share @rohith1001 Thanks bro. One more doubt - Can we say that p$^{*}$q$^{*}$ $=$ p$^{*}$ + q$^{*}$? 0 votes 0 votes rohith1001 commented Dec 6, 2019 reply Follow Share No. LHS matches pq but RHS is not matching pq. But how is it related to this question? :O 0 votes 0 votes ayushsomani commented Dec 6, 2019 reply Follow Share No. It's not related to this question. Actually, I came across somewhere and thought of writing that. 😁 0 votes 0 votes neel19 commented Aug 11, 2021 reply Follow Share Can anyone give the solution using the intersection of 2 DFA method? I am not getting a minimal solution. 0 votes 0 votes Abhrajyoti00 commented Oct 18, 2022 reply Follow Share First Negate The Given Statement : ~(Strings that contain neither the substring $00$ nor the substring $11$) $\implies $ Strings that contain the substring $00$ or the substring $11$So the regular expression is : $L’ = (0+1)^*(00+11) (0+1)^*$Then drawing it’s DFA is very easy :-After this if you complement the machine (change all the final and non final states without touching the arrows), you will get the required min-DFA.DFA made from : FSM Simulator (ivanzuzak.info) 2 votes 2 votes Please log in or register to add a comment.
2 votes 2 votes j>=i is the condition.solve using some examples there will never be a condition when # of a's would be greater than # of b's jenny101 answered Apr 30, 2016 jenny101 comment Share Follow See all 0 reply Please log in or register to add a comment.