GATE CSE 2000 | Question: 7

Question

• A. 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$.
• B. 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$?

Comments

1. There is no such thing as “the” minimal NFA for a given regular language, because minimal NFA is not unique for a regular language.

2. When a question asks for a "minimal finite state machine," it is referring to a minimal Deterministic Finite Automaton (DFA).

The reason for this is that Only DFAs have a unique minimal form. For any given regular language, there is a unique minimal DFA, whereas an NFA does not have a unique minimal form. Minimization is a well-defined process for DFAs, involving merging equivalent states to reduce the number of states.

3. As per many authors like Hopcroft, Ullman, By default, "finite automaton" means "DFA". So, assuming FA as DFA won't lose you marks in the GATE exam, as you can challenge it using standard resources. 

---

@Deepak Poonia Sir, here they have taken NFA as minimal by default.

Answer 1

1. 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.
   
2. $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.$

Comments

No. It's not related to this question. Actually, I came across somewhere and thought of writing that. 😁

---

Can anyone give the solution using the intersection of 2 DFA method? I am not getting a minimal solution.

---

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)

Answer 2

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