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 for 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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,110 questions

44,694 answers

127,230 comments

43,752 users