The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 votes
  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?

asked in Theory of Computation by Veteran (68.8k points)
retagged by | 493 views

2 Answers

+22 votes
Best answer

(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

answered by Boss (5.7k points)
selected by
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.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,619 questions
39,267 answers
36,653 users