Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$A$ is an alphabet. An automaton over $A$ can be defined as a set $A_0 = (Q, E, I, T),$ where $Q$ is the set of states, $E \subseteq Q \times A \times Q$ is the set of edges or transition, $I, T \subseteq Q$ of initial and terminal states. A path in the automaton $A_0$ is a sequence $(p_0, a_1, p_1),$ $(p_1, a_2, p_2),$ $\ldots,$ $(p_{n-1}, a_n, p_n)$ of consecutive edges. A state $p$ is accessible if there is a path starting in an initial state and ending in $p.$ It is coaccessible if there is a path starting in $p$ and ending in a terminal state. An automaton is trim if every state is accessible and coacessible.

The information above is from M. Lothaire's Algebraic Combinatorics on Words. My question is whether $(p, \epsilon, p)$ is a path or not. Since $\epsilon$ is not in $A,$ my answer is no. If so, is an inital state accessible? According to the definition above, we may say it will be if there is a path starting from an initial state and ending in the initial state.Then if an automaton is trim,the initial states should be accessible.But in the following statement about the trim automaton,I don't think the $trim$ ensures the initial state(s) is(are) necessary accessible.

So actually I want to make sure whether the $(p,\epsilon,p)$ is a path. Second, if the initial states are only coaccessible(i.e there may be no path starting from an initial state and ending in the initial states), is the automaton still trim?

These two questions make me too confused to continue to read the following content in the book. Thanks in advance.


If I applied $\epsilon$ into the definition.Then the example of the first returns to state 1 below shouldn't be $X=${$b,ab$} but $X=${$\epsilon,b,ab$} which contradicts with the former $X=${$b,ab$} given in the book.The set of $first$ $returns$ to a state $q$ is the set of labels(or words) of paths from $q$ to $q$ which do not pass another time through $q$.
enter image description here
On the other hand,without the $\epsilon$ path,I don't know how to ensure the automaton in the following proof is trim,since the initial state doesn't seem to be accessible without the $\epsilon$ path.

enter image description hereenter image description here




All the information above is shown in http://x.co/iEVa, from Page 12 to Page 14.
Thank you for reading this long post.

share|improve this question
    
I made an edit: replaced the image with text. If it gets approved, please check to make sure I haven't changed your question. –  user2468 Mar 17 '12 at 17:49
    
Nice catch -- it could have been a mistake by the author, or it could have been intentional. In either case, it's a good question to ask, and shows you are being attentive and thinking things through. But don't let it hang you up. –  David Lewis Mar 17 '12 at 18:25
    
@ J.D.:Yes,thanks for your transformation.I just saved the image copy due to some problems with my computer. –  Andylang Mar 18 '12 at 8:59
    
Many definitions of NFA include $\varepsilon$-transitions, but they are not necessary (just convenient). As stated, your definition does indeed exclude them. –  Raphael Mar 18 '12 at 10:09

1 Answer 1

up vote 4 down vote accepted

The definition of a path doesn't say that the sequence can't be an empty sequence. But then, it is troublesome to ask "what is the starting point of the empty sequence ?", and your text doesn't clear that up. It is preferrable to have one empty path from each state into itself :

A clearer definition may be : a path from $p$ to $q$ is a finite sequence of states $(p_0, \ldots, p_n)$ with a word of length $n$, $w = a_1 \ldots a_n$ such that $p=p_0, q=p_n,$ and $(p_{i-1}, a_i,p_i) \in E$ for all $i \in \{1 \ldots n\}$.

With this definition, you can clearly have empty paths from a state to itself, and the "starting state" and "ending state" of a path is a part of the definition, so you can use it for the discussion that follows. And in particular, all initial states are accessible, and all final states are coaccessible.

Also, if your automaton is not deterministic, it's not avisable to describe a path with only the starting state, the ending state, and the word $w$ associated to the path, since it doesn't necessarily tell you what are all the intermediate states.


In Proposition 1.3.2, the text hints that $Q(\epsilon)$ should be defined since the empty word is a word, so the set $Q(\epsilon)$ of states $q$ for which there is a path from an initial state to $q$ whose associated word is $\epsilon$ should be meaningful (in fact, you get $Q(\epsilon) =\{I\}$ )

Another problem is that $\mathscr{B}$ may have states that are not coaccessible. Each state $Q(u)$ is accessible from $\{I\}$ with a path whose associated word is $u$. But if, for example, there is no terminal state in the first place, then you don't get any terminal state in $\mathscr{B}$ and so no state is coaccessible. If you remove all the non coaccessible states from $\mathscr{B}$, you then get a trim automaton.

For example, a trim automaton recognizing the empty language is $(\emptyset, \emptyset, \emptyset, \emptyset)$


For the set of first returns, yes it seems that on the contrary, empty labels or empty paths are not allowed in the definition of the set of first returns.

So you have to be careful and actively check if the author allows "the empty path" in any definition involving paths, and pick the one that makes the following discussion consistent. From my limited experience, it is usually allowed. Though this books seems to have a rather wide range of subjects, so I can't divine that it is always the case.

Keep in mind that it is very hard (read impossible) to write an entire book without making a few mistakes / omissions here and there especially on edge cases like this.

share|improve this answer
    
This is the right thing to do if you want the empty word to be considered in the language defined by the automaton whenever $I \cap T \neq \phi$. That's usually the case, but not necessarily. It might depend, for example, whether you are dealing with monoids, which have a multiplicative identity (the empty word, for example) or semigroups, which don't. You might accept mercio's answer for now, but keep an eye out as you read the text to see how the empty word is handled in various contexts. The author may have intended to exclude it, as the def indicates, or it could have been a mistake. –  David Lewis Mar 17 '12 at 18:23
    
@ David Lewis:Yes.Sometimes if the empty word is included,it will be no problem for the proofs of some propositions.But in an example of the book,it seems that the empty word should be excluded as a path. –  Andylang Mar 18 '12 at 9:53
    
@ mercio: The example above doesn't seem to support the $\epsilon$ path –  Andylang Mar 18 '12 at 10:42
    
@ mercio:Yes,I agree with your opinion now.I think I will accept the $\epsilon$ path. And I will modify the definition of $first$ $returns$ to be a set above without empty word.And for the proof of proposition 1.3.2,to remove the nonaccessible states(or maybe failure states) does get a trim automaton.Thank you very much! –  Andylang Mar 18 '12 at 15:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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