The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
52 views
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.6k points) | 52 views

1 Answer

0 votes
  • At first you make a DFA for this . After we can find regular expression .

 

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

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:

0
answer is correct..!


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

36,995 questions
44,570 answers
126,774 comments
43,636 users