+17 votes
694 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$?

asked
edited | 694 views

## 2 Answers

+23 votes
Best answer
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$

answered by Loyal (6.1k points)
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
+3 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
answered by Active (1.4k points)

+23 votes
6 answers
1
+16 votes
3 answers
2
+1 vote
1 answer
3
+2 votes
0 answers
4
+17 votes
4 answers
5
+11 votes
3 answers
6
+4 votes
1 answer
7