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$?

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

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

---

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

---

@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?

---

@ayushsomani

Refer these two images.

Page1: https://gateoverflow.in/?qa=blob&qa_blobid=13292319058827833562

Page2: https://gateoverflow.in/?qa=blob&qa_blobid=2858136095014749190

---

@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. :(

---

@rohith1001

So, if it is asked Minimal Finite Automata, then i can draw a minimal DFA coz minimal DFA == minimal NFA?

 

---

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.

---

@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.

---

I think you are right. For this question removing the dead state gives us the minimal NFA.

---

@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?

---

Yes. The cross product has m $\times$ n states, but it need not be a minimum DFA. Hence we will have to minimize it.

---

@rohith1001

Thanks bro.

One more doubt - Can we say that p$^{*}$q$^{*}$ $=$ p$^{*}$ + q$^{*}$?

---

No. LHS matches pq but RHS is not matching pq.

But how is it related to this question? :O

---

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