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.8k 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 Show 13 previous comments 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.