The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
74 views
can 0*1+1* generate 01 and 11 and 011?

what would be the minimal dfa ?
asked in Theory of Computation by (27 points)
edited by | 74 views
0
Yes..
0
Yes it will generate 01 and 11.

Check this 0*1 will give 01 and 1* will generate 11.
0

Siddharth Bhardawaj  I agree with you on the first part but why 1+1* to generate 11? Only 1* is enough to generate 11 right?

0
@MiniPanda
Yes, you are correct... Thanks though for correcting me and I corrected my comment....
0

1+1* means 1 + {epsilon, 1,11,111...}. Here the bold 1 doesn't have any contribution in generating 11. That is why i thought it isn't necessary to mention that 1 explicitly. Am i wrong?

+1
@MiniPanda

Yes , you are correct.
0
aint the dfa going to have 5states.
0

yes it can generate 01 and 11, but not 011

and DFA will be of 5 state 

let 5 state be q0,q1,q2,q3,qd

  0 1
$\rightarrow$q0* q1 q2
q1 q1 q3
q2* qd q2
q3* qd qd
qd qd qd

qd refers to dead state

 

0
@tesla wont this dfa accepts 101 which is not in RE
0

Yes, you are correct @arvin, let me correct it

+1
@tesla i think it will have 5states with 3 final states.
0
I am getting 4 states but my transitions are different.
0
@minipanda can u provide ur dfa
0
  0 1
->q0* q2 q1
q1* qdead q1
q2 q2 q1
qdead qdead qdead

Is it accepting any invalid string?

0

@MiNiPanda yes it accepts 011,0111,01111... and so on which are not part of the language.

0
@minipanda yes dear i think it will accept 0111.... which is invalid.
0
Yup right.. Thanks  Tesla! and  arvin
0

dfa will look like this :p what i drew earlier

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
0 votes
0 answers
2
asked Dec 18, 2017 in Theory of Computation by Pawan Kumar 2 Active (4.6k points) | 54 views


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,625 questions
48,616 answers
155,897 comments
63,872 users