GATE CSE
First time here? Checkout the FAQ!
x
0 votes
81 views
If n state finite automata accespts infinite language then what is the length of min, and max. cycle?
asked in Theory of Computation by Loyal (3.1k points)   | 81 views
Min :2 ; Max: n ?
if there is a self loop minimum should be 1 and max=n. ??
I dont have the exact answer,Read this questions somewhere:(
Can we call self-loop a cycle?
all cycles are loops and loop is self and non self also.
min - 1

max - no limit since this is infinite language

1 Answer

0 votes
if there is no self loop.

then min.-N   and max.-2N-1
answered by Junior (865 points)  
Can you please provide some valid reason for this answer to understand?
Your answer is right as i got some theorem related to this.Request you to please explain.
I have added theorem here:-http://gateoverflow.in/104257/toc-finite-automata-infinite-language
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.
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:(


Top Users Apr 2017
  1. akash.dinkar12

    3518 Points

  2. Divya Bharti

    2558 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1608 Points

  8. Arunav Khare

    1464 Points

  9. Arjun

    1430 Points

  10. Kapil

    1424 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,047 answers
63,238 comments
24,137 users