4
$\begingroup$

$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.

  • 0
    Many definitions of NFA include $\varepsilon$-transitions, but they are not necessary (just convenient). As stated, your definition does indeed exclude them.2012-03-18

1 Answers 1

4

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.

  • 0
    @ 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!2012-03-18