845 views
1. Construct as minimal finite state machine that accepts the language, over $\{0,1\}$, of all strings that contain neither the sub string $00$ nor the sub string $11$.
2. Consider the grammar
      S →           aSAb
S →              ∊
A →             bA
A →              ∊


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^i$ for some $i, j \geq 0$, where $i$ and $j$ satisfy some condition. What is the condition on the values of $i$ and $j$?

edited | 845 views

1. langauge $L = (0+1)^*- (0+1)^*(00+11) (0+1)^*$   .................... is it true ??  DFA contains $4$ states , $3$ are final , $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 \wedge$ can generate any no of $b$'s including null , if $A$ is $\wedge$ then $i=j$ and if $A$ is generate any $b$ then $j>i$ so  condition is $i\leq j$

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

1
2
+1 vote