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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

- 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$.
- 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$?

+23 votes

Best answer

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

- $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$

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,168 comments

67,679 users