1.2k views

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

0
0* 1 1* 0 (0+1)* this is the language in which every 1 is must followed by 0

@Bikram sir my doubt is how to complement this ?
0
0* 1 1* 0 (0+1)* why this is wrong
0
i also make the sm mistake :P

$L=0^*1^*$

$L$ contains all binary strings where a $1$ is not followed by a $0$.
edited by
+6
It can also be 0*11*+0*
+7
@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
Yes, I am also getting this answer.
A grammer not containing 10 as substring

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*

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*

0

How did you simplified B = A1 + B1 = 0*1 +B1 = 0*11*.

according to Arden's theorem shouldn't it be: B=B.1+0*11* =1*0*1 ?

0

B= 0*1 + B1

R=B, Q=0*1 and P=1

then by arden's theorem,

0*11*

0

u have to union both the A and B values becoz there are two final states n given FA