@Bikram sir my doubt is how to complement this ?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

The regular expression for the language recognized by the finite state automaton of figure is ______

+31 votes

Best answer

Using Arden's theorem to find the regular expression :

$A = \epsilon + A0 = \epsilon0^* = 0^*$

$B = A1 + B1 = 0^*1 +B1 = 0^*11^* $

As there are two final states, we should union both RE.

$\implies 0^∗+0^∗11^∗=0^∗(\epsilon +11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗%=0^∗+0^∗11^∗=0^∗(\epsilon+11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗ $

Note that $\epsilon+1^+=1^∗$

PS : Ardens theorem - Let $P$ and $Q$ be two regular expressions. If $P$ does not contain null string, then $R = Q + RP$ has a unique solution which is $R = QP^*$

$L=0^*1^*$

$L$ contains all binary strings where any $1$ is not followed by any $0$.

$A = \epsilon + A0 = \epsilon0^* = 0^*$

$B = A1 + B1 = 0^*1 +B1 = 0^*11^* $

As there are two final states, we should union both RE.

$\implies 0^∗+0^∗11^∗=0^∗(\epsilon +11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗%=0^∗+0^∗11^∗=0^∗(\epsilon+11^∗)=0^∗(\epsilon+1^+)=0^∗1^∗ $

Note that $\epsilon+1^+=1^∗$

PS : Ardens theorem - Let $P$ and $Q$ be two regular expressions. If $P$ does not contain null string, then $R = Q + RP$ has a unique solution which is $R = QP^*$

$L=0^*1^*$

$L$ contains all binary strings where any $1$ is not followed by any $0$.

+10

@gatemate u right R.E for each final state and apply in b/w '+' mans OR then u got 0*+0*11* then take common 0*(epsilion+11*) ans as we know (epsilon+rr*)=r* so here we get 0*1*

0 votes

Clearly , looking into DFA we can say that C is Dead state.

Using Arden's theoram to find the regular expression :

A = ε** **+** **A0** = **ε0*** = **0*

B = A1 + B1 = 0*1 +B1 = 0*11* = 0*1*

Therefore answer is 0*1*

PS : Ardens theoram -

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,136 answers

187,341 comments

71,060 users