The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.7k views

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

asked in Theory of Computation by Veteran (52k points)
edited by | 1.7k views
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

4 Answers

+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$.
answered by Boss (42.3k points)
edited by
+8
It can also be 0*11*+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
Yes, I am also getting this answer.
0
Tell me if there is a mistake in my logic as C is dead state we don't need to consider expression going into that state.

Hence expression will be 0*.1.1* is a.a*=a+

 

hence it reduces to 0*.1+?

 

Please correct me
0

@sripo your regular expression is not accepting epsilon it should be 0*1*

0
$r_a=0^*$

$r_b=0^*11^*$

$L=r_a+r_b=0^*+0^*11^*=0^*(\epsilon+11^*)=0^*1^*$
+1 vote

regular expr= 0*1*

answered by Boss (33.9k points)
0 votes
A grammer not containing 10 as substring
answered by Active (1.8k points)
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*

answered by Active (2.1k points)
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*

+1

@Shubhgupta

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

0
yes, @once_2019, you're correct. We should union both.

$= 0^* + 0^*11^* = 0*(e + 11^*) = 0^*(e+1^+) = 0^*1^*$

Note that $e + 1^+ = 1^*$

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,532 questions
54,136 answers
187,341 comments
71,060 users