The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression?
asked in Theory of Computation by Active (2.7k points) | 88 views

1 Answer

+1 vote
  • At first you make a DFA for this . After we can find regular expression .


answered by Boss (24k points)
From the third state can't we make a transition to the 2nd state on 0 without adding one extra state ?
well in DFA for accepting 101 we can make transition of 0 from 3rd state to 1st we will need 4 states only...dnn need that extra stage
Yes sorry.. 1st state not 2nd..
@mini panda yes that can be done..!

well, I was also able to come up with the DFA, point was how do I reduce this DFA to regex. I have come up with following reduction of dfs to regex. Tell me if it looks correct:

answer is correct..!

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

42,572 questions
48,561 answers
63,580 users