1
$\begingroup$

If we have a finite automaton that accepts a string,

is there any numerical relationship that always is true like S ≥ |w| or something similar?

Where |w| the length of the string and S the number of transited states (counting multiplicities).

For example, if we have this automata and the string w = 010 :

enter image description here

S = 3 and |w| = 3.

In this case, S = |w|

I'm new in computer science and i was thinking there has to be a rule of that kind but I have not found explicitly in the books that I started on computational theory.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to CS.SE! What are your thoughts? What analysis and research have you done so far? A one-sentence question usually isn't a good fit here; we want you to provide background and context (what's the motivation for the question? where did you run across this), exhaust all reasonable ways you could solve this on your own, and show us in the question what you've tried so far, what progress you've made, and where you got stuck. Also, the body of the question should be a self-contained question, and the title should be a short summary, not a full sentence. $\endgroup$ – D.W.♦ Aug 26 '16 at 18:09
  • 2
    $\begingroup$ Finally, it's not clear to me what you are asking. What do you mean by "transited during analysis"? Why do you believe there is a single numerical ratio that is correct for all possible automata? What kind of answer are you looking for? Please edit the question to address this feedback. $\endgroup$ – D.W.♦ Aug 26 '16 at 18:10
  • $\begingroup$ I also cannot figure out what is your question. $\endgroup$ – Yuval Filmus Aug 26 '16 at 18:20
  • $\begingroup$ Thanks for the coments. I will try to be more clear next time and get better with my english also... $\endgroup$ – Samuel Salvatella Aug 26 '16 at 18:26
  • 2
    $\begingroup$ Thanks for the edits, that helps a lot! By S, do you mean the number of different states (so if a state is visited 20 times you only count it once)? Or do you also want to count multiplicities? For instance, if one state is visited 20 times and another state is visited 30 times, should S be 20+30=50 or should it be 1+1=2? Also, have you tried working through some examples? You should try to work out the answer on your own. A good approach is to try some small examples, then make a conjecture and see if you can prove it; and see if you can find any example that violates it. $\endgroup$ – D.W.♦ Aug 26 '16 at 18:39
1
$\begingroup$

The way you have defined S, we will always have $S \ge |w|$. Why? Because each time the automaton reads one symbol from $w$, it follows one transition and visits the state at the end of that transition, incrementing $S$ by one. In other words, we add one to $S$ for each symbol in $w$. Thus $S$ is at least as large to the number of symbols in $w$. (It might be larger if you follow $\epsilon$-transitions, as they don't consume any symbols in $w$ but do visit a state.)

Try working through a few examples and it should become clearer.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for yout answer. We will always have S=|w|independently the automaton? If we have an automaton with ε -transitions it is posible to have S > |w|, no? $\endgroup$ – Samuel Salvatella Aug 28 '16 at 17:07
  • $\begingroup$ @SamuelSalvatella, yes, you're completely right; we can have $S >|w|$. Thank you for highlighting this. I've edited my answer accordingly -- see the edited answer. $\endgroup$ – D.W.♦ Aug 28 '16 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.