The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 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 $\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 in Theory of Computation by Veteran (52.1k points)
edited by | 905 views

2 Answers

+24 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 Active (5k points)
edited 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
+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
answered by Active (1.1k 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
49,814 questions
54,518 answers
75,287 users