in Theory of Computation edited by
2,625 views
23 votes
  1. 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$.
  2. 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$?

in Theory of Computation edited by
2.6k views

2 Answers

37 votes
 
Best answer
  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.$
edited by

15 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
0
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

@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
edited by

@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

@rohith1001

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

 

0
edited by

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

@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
I think you are right. For this question removing the dead state gives us the minimal NFA.
0

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

@rohith1001

Thanks bro.

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

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

But how is it related to this question? :O
0
No. It's not related to this question. Actually, I came across somewhere and thought of writing that. 😁
0
Can anyone give the solution using the intersection of 2 DFA method? I am not getting a minimal solution.
0
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

Related questions