493 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 ∊ is the empty string. This grammar generates strings of the form aibj for some i, j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?

retagged | 493 views

(a)  langauge L = (0+1)- (0+1)*(00+11) (0+1)*   .................... is it true ??  DFA contains 4 states , 3 are final , 1 is dead state

(b) i <= j

as S->aSAb

there will be always for one a in left and minimum one b in right and A->bA |^ can generate any no of b's including null , if A is ^ then i=j and if A is generate any b then j>i so  condition is i<=j

selected
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