0 votes 0 votes If n state finite automata accespts infinite language then what is the length of min, and max. cycle? Theory of Computation theory-of-computation finite-automata + – rahul sharma 5 asked Jan 11, 2017 rahul sharma 5 1.0k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Kantikumar commented Jan 11, 2017 reply Follow Share Min :2 ; Max: n ? 0 votes 0 votes santhoshdevulapally commented Jan 11, 2017 reply Follow Share if there is a self loop minimum should be 1 and max=n. ?? 0 votes 0 votes rahul sharma 5 commented Jan 11, 2017 reply Follow Share I dont have the exact answer,Read this questions somewhere:( 0 votes 0 votes Kantikumar commented Jan 11, 2017 reply Follow Share Can we call self-loop a cycle? 0 votes 0 votes santhoshdevulapally commented Jan 11, 2017 reply Follow Share all cycles are loops and loop is self and non self also. 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share min - 1 max - no limit since this is infinite language 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes if there is no self loop. then min.-N and max.-2N-1 Rajnish Kumar answered Jan 11, 2017 Rajnish Kumar comment Share Follow See all 4 Comments See all 4 4 Comments reply rahul sharma 5 commented Jan 11, 2017 reply Follow Share Can you please provide some valid reason for this answer to understand? 0 votes 0 votes rahul sharma 5 commented Jan 12, 2017 reply Follow Share Your answer is right as i got some theorem related to this.Request you to please explain. I have added theorem here:-https://gateoverflow.in/104257/toc-finite-automata-infinite-language 0 votes 0 votes Rajnish Kumar commented Jan 12, 2017 reply Follow Share you should go through pumping lemma theorem. take any example- N=4 try all possibility of loops except self loop THEN you 'll get it. 0 votes 0 votes rahul sharma 5 commented Jan 13, 2017 reply Follow Share I tried on this,please confirm Say I have four states a,b,c,d in my machine now after traversing from a to d ,the string went back to some state(start state),means as of now it is not accespted,now when it again come to d,we came to know that some loop has been pumped.Is it correct understanding? But then when i went from a->d and then came to a,isnt it sufficient to say that we have a loop,?Why do we want to enter final state again.Please explain once .I have gone through pumping lemma theorem ,but this is best i could think as of now:( 0 votes 0 votes Please log in or register to add a comment.