# Directing Words of Fuzzy Finite Automata

Magnus Steinby
Department of Mathematics and Statistics
University of Turku
FI-20014 Turku, Finland

###### Abstract

A deterministic finite automaton is _directable_ if it has a _directing word_
which takes the automaton from every state to the same state. These notions
have been extended also to other kinds of automata. Thus, B. Imreh and M.
Steinby (1999) identified three natural types of directing words, called D1–,
D2– and D3–directing words, for nondeterministic finite automata (NFAs). Here
we adapt these notions for fuzzy finite automata (FFAs). The D3–directing
words obtained this way are precisely the directing words introduced by V.
Karthikeyan and M. Rajasekar (2015). With any FFA ${\mathcal{F}}$ we associate
an NFA ${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ which has the same
D$i$–directing words as ${\mathcal{F}}$. Thus, if these definitions are used,
the theory of directable FFAs reduces to that of NFAs.

We also introduce three new kinds of directing words of fuzzy automata that we
call DD1–, DD2– and DD3–directing words, respectively which depend more on the
fuzzy transition degrees between states. We establish some basic properties of
the sets $DD_{i}({\mathcal{F}})$ of DD$i$–directing words of any given FFA
${\mathcal{F}}$. In particular, it is shown that these languages are regular,
and that DD$i$–directability is decidable. For so-called _normal FFA_ s the
languages $DD_{i}({\mathcal{F}})$ are shown to have some special properties.
Several relationships between the families of the corresponding sets
$DD_{i}({\mathcal{F}})$ of DD$i$–directing words are presented. We also
determine the complete $\cap$-semilattice of the various classes of
DD$i$–directable FFAs and normal FFAs and their intersections.

Keywords: fuzzy automaton, directing word, directable automaton,
nondeterministic automaton

2010 Mathematics Subject Classification: 68Q45

##  1 Introduction

An input word $w$ of a deterministic finite automaton (DFA) ${\mathcal{A}}$ is
said to be _directing_ , or _synchronizing_ , if it takes ${\mathcal{A}}$ from
every state to a fixed state $c$, and ${\mathcal{A}}$ is _directable_ if it
has directing words. The topic has been extensively studied ever since it was
introduced by Černý [4] in 1964. Directability has also been defined for other
kinds of automata. In particular, Imreh and Steinby [12] identify three types
of directing words of nondeterministic finite automata (NFAs). In [16]
Karthikeyan and Rajasekar define directing words for fuzzy finite automata
(FFAs), and using this notion they attempt to fuzzify the contents of [11]
(without mentioning this paper).

The three types of directing words of NFAs, the D1–, D2– and D3–directing
words, considered in [12], can be defined in a natural way for fuzzy automata,
too. Then the directing words of [16] are the same as the D3–directing words.
We show that for every FFA there is an NFA such that the two automata have
exactly the same directability properties. Hence, all the results aimed at in
[16], and much more, follow from known facts about NFAs (cf. [3, 5, 6, 7, 10,
12, 13, 14, 25], for example).

Then we introduce three new types of directing words of fuzzy automata that
depend more on the transition degrees between states. The study of the sets of
such directing words, the families of languages formed by them, and the
classes of the corresponding directable FFAs form the main contents of this
paper.

Section 2 introduces some basic terminology, notation and the automata to be
considered. In Section 3 we first recall the definitions of directing words
for DFAs as well as the D1–, D2– and D3–directing words of NFAs. Then we
define D1–, D2– and D3–directing words of FFAs. With each FFA ${\mathcal{F}}$
we associate an NFA ${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ that faithfully
reflects some important properties of the original automaton. In particular,
for each $i=1,2,3$, the FFA ${\mathcal{F}}$ and the NFA
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ have the same D$i$–directing words,
which means that the properties of D$i$–directable FFAs and their directing
words can be derived directly from the theory of D$i$–directable NFAs. We also
note that for any FFA ${\mathcal{F}}$, the languages $D_{1}({\mathcal{F}})$,
$D_{2}({\mathcal{F}})$ and $D_{3}({\mathcal{F}})$ of D1–, D2– and D3–directing
words of ${\mathcal{F}}$ are regular, and that D$i$–directability is therefore
decidable. Finally, it is shown how an algorithm for testing the directability
of a DFA presented in [11] can be modified for deciding whether a given
(complete) FFA is D3–directable.

In Section 4 we introduce DD1–, DD2– and DD3–directing words of FFAs, and
DD1–, DD2– and DD3–directable FFAs, and present some properties of the sets
$DD_{1}({\mathcal{F}})$, $DD_{2}({\mathcal{F}})$ and $DD_{3}({\mathcal{F}})$
of the respective sets of directing words of an FFA ${\mathcal{F}}$. Among
other matters, we exhibit relationships between the languages
$DD_{i}({\mathcal{F}})$ and $D_{i}({\mathcal{F}})$. Also the languages
$DD_{i}({\mathcal{F}})$ are shown to be regular.

In Section 5, we study the relationships between the families of languages
formed by the sets $DD_{i}({\mathcal{F}})$ of DD$i$-directing words of such
FFAs. In Section 6 we establish the inclusion relationships between the
classes of DD$i$-directable FFAs and the classes of DD$i$-directable so-called
normal FFAs.

Some familiarity with the basic theory of finite automata and regular
languages is assumed (cf. [1], [8], [18], [23] or [24], for example). For the
general theory of fuzzy automata and fuzzy languages, the reader may consult
[20] or [22]. The papers [2] and [26] survey parts of the theory of directable
automata. Much of our terminology and notation stems from [11, 12].

##  2 Some basic notions

We may write $A:=B$ to emphasize that $A$ is defined to be equal to $B$. The
cardinality of a set $A$ is denoted by $|A|$, and the set of all subsets of
$A$ by $\wp(A)$. For any integer $n\geq 0$, let
${\mathbf{n}}:=\\{1,\ldots,n\\}$.

In what follows, $X$ is always a finite nonempty alphabet. The set of all
(finite) words over $X$ is denoted by $X^{*}$ and the empty word by
$\varepsilon$. Furthermore, let $X^{+}:=X^{*}\setminus\\{\varepsilon\\}$. The
length of a word $w\in X^{*}$ is denoted by $\mathrm{lg}(w)$. Subsets of
$X^{*}$ are called _languages_. A _family of languages_ ${\mathcal{L}}$
assigns to each finite nonempty alphabet $X$ a set ${\mathcal{L}}(X)$ of
languages over $X$. We write ${\mathcal{L}}=\\{{\mathcal{L}}(X)\\}_{X}$.

A _fuzzy language_ over $X$ is a mapping $\lambda:X^{*}\rightarrow[0,1]$,
where the set of _degrees of membership_ is the real unit interval $[0,1]$
ordered by the usual $\leq$-relation and equipped with the lattice operations
$r\vee s=\max(r,s)$ and $r\wedge s=\min(r,s)$. Thus we follow Zadeh’s [27]
original definition. The _support_ of $\lambda$, is the language
$\mathrm{supp}(\lambda):=\\{w\in X^{*}\mid\lambda(w)>0\\}$, and its _range_ is
the set $\mathrm{ran}(\lambda):=\\{\lambda(w)\mid w\in X^{*}\\}$. If
$\mathrm{supp}(\lambda)$ is a finite set $\\{w_{1},\ldots,w_{n}\\}$, we may
write

$\lambda=\\{w_{1}/\lambda(w_{1}),\ldots,w_{n}/\lambda(w_{n})\\}.\vspace{-3pt}$

If $\mathrm{ran}(\lambda)\subseteq\\{0,1\\}$, then $\lambda$ is said to be
_crisp_.

A _deterministic finite automaton_ , a _DFA_ for short,
$\mathcal{A}=(A,X,\delta)$ consists of a finite nonempty set $A$ of _states_ ,
the _input alphabet_ $X$, and a _transition function_ $\delta:A\times
X\rightarrow A$ which is extended in the usual way to a mapping
$\delta^{*}:A\times X^{*}\rightarrow A$.

A _deterministic finite recognizer (DFR)_ ${\mathbf{A}}=(A,X,\delta,a_{0},F)$
is a DFA $\mathcal{A}=(A,X,\delta)$ equipped with an _initial state_ $a_{0}\in
A$ and a set $F\subseteq A$ of _final states_. It _recognizes_ the language
$L({\mathbf{A}}):=\\{w\in X^{*}\mid\delta^{*}(a_{0},w)\in F\\}$, and a
language $L\subseteq X^{*}$ is said to be _recognizable_ , or _regular_ , if
$L=L({\mathbf{A}})$ for such a recognizer ${\mathbf{A}}$. The set of regular
languages over $X$ is denoted by $Rec(X)$.

A _nondeterministic finite automaton (NFA)_ $\mathcal{N}=(A,X,\alpha)$
consists of a finite nonempty set $A$ of _states_ , the _input alphabet_ $X$,
and a nondeterministic _transition function_ $\alpha:A\times
X\rightarrow\wp(A)$. The transition function is extended to a mapping
$\alpha^{*}:\wp(A)\times X^{*}\rightarrow\wp(A)$ as follows: for every
$H\subseteq A$,

  * (1)

$\alpha^{*}(H,\varepsilon)=H$, and

  * (2)

$\alpha^{*}(H,ux)=\bigcup\\{\alpha(b,x)\mid b\in\alpha^{*}(H,u)\\}$ for any
$u\in X^{*}$ and $x\in X$.

For any $H\subseteq A$ and $w\in X^{*}$, $\alpha^{*}(H,w)$ is the set of
states reachable by the input word $w$ from some state in $H$. For any $a\in
A$ and $w\in X^{*}$, we write $\alpha^{*}(a,w)$ for $\alpha^{*}(\\{a\\},w)$.
The NFA ${\mathcal{N}}$ is complete, if $\alpha(a,x)\not=\emptyset$ for all
$a\in A$ and $x\in X$. Obviously, then $\alpha^{*}(a,w)\not=\emptyset$ for all
$a\in A$ and $w\in X^{*}$.

A _fuzzy finite automaton (FFA)_ $\mathcal{F}=(A,X,f)$ consists of a finite
nonempty set $A$ of _states_ , the _input alphabet_ $X$, and a fuzzy
_transition function_

$f:A\times X\times A\rightarrow[0,1].\vspace{-3pt}$

In concrete examples of an FFA $\mathcal{F}=(A,X,f)$, we specify the
transition function $f$ by giving the nonzero values $f(a,x,b)$.

The transition function is extended to $f^{*}:A\times X^{*}\times
A\rightarrow[0,1]$ by setting

  * (1)

$f^{*}(a,\varepsilon,a)=1$, and $f^{*}(a,\varepsilon,b)=0$ if $b\neq a$, and

  * (2)

$f^{*}(a,w,b)=\max\\{f^{*}(a,v,c)\land f(c,x,b)\\}\mid c\in A\\}$ for $w=vx$
with $v\in X^{*}$ and $x\in X$,

for all $a,b\in A$. For any $a\in A$ and $w\in X^{*}$, let

${\mathcal{F}}(a,w):=\\{b\in A\mid f^{*}(a,w,b)>0\\}.\vspace{-3pt}$

Thus ${\mathcal{F}}(a,w)$ is the set of states reachable (to a nonzero degree)
from state $a$ by the input word $w$. With any pair $a\in A$ and $w\in X^{*}$,
we also associate a fuzzy subset

${\mathcal{F}}_{a,w}:A\rightarrow[0,1],\>b\mapsto f^{*}(a,w,b),\vspace{-3pt}$

of $A$. Obviously, $\mathrm{supp}({\mathcal{F}}_{a,w})={\mathcal{F}}(a,w)$.

For any $H\subseteq A$ and $w\in X^{*}$, let
${\mathcal{F}}(H,w):=\bigcup\\{{\mathcal{F}}(a,w)\mid a\in H\\}$.

The fuzzy automaton ${\mathcal{F}}$ is _complete_ if
${\mathcal{F}}(a,x)\neq\emptyset$ for all $a\in A$ and $x\in X$. If
${\mathcal{F}}$ is complete, then clearly ${\mathcal{F}}(a,w)\neq\emptyset$
for all $a\in A$ and $w\in X^{*}$.

##  3 Directing words and directable automata

A word $w\in X^{*}$ is a _directing word_ of a DFA $\mathcal{A}=(A,X,\delta)$
if there is a state $c\in A$ such that $\delta^{*}(a,w)=c$ for every $a\in A$.
The set of directing words of ${\mathcal{A}}$ is denoted by
$DW({\mathcal{A}})$, and ${\mathcal{A}}$ is _directable_ if
$DW({\mathcal{A}})\neq\emptyset$.

In [12] three kinds of directing words of an NFA $\mathcal{N}=(A,X,\alpha)$
were identified. A word $w\in X^{*}$ was said to be

  * (D1)

_D1–directing_ if $(\exists c\in A)(\forall a\in A)(\alpha^{*}(a,w)=\\{c\\})$,

  * (D2)

_D2–directing_ if $(\forall a,b\in A)(\alpha^{*}(a,w)=\alpha^{*}(b,w)$, and

  * (D3)

_D3–directing_ if $(\exists c\in A)(\forall a\in A)(c\in\alpha^{*}(a,w))$.

For each $i=1,2,3$, the set of D$i$–directing words of ${\mathcal{N}}$ is
denoted by $D_{i}({\mathcal{N}})$, and ${\mathcal{N}}$ is called D$i$–
_directable_ if $D_{i}({\mathcal{N}})\neq\emptyset$.

If we regard a DFA as a special NFA, all three conditions (D$i$) yield the
usual directing words. To state this more precisely, we associate with each
DFA $\mathcal{A}=(A,X,\delta)$ an NFA
${\mathcal{A}}^{{\mathbf{n}}{\mathbf{d}}}=(A,X,\alpha)$, where $\alpha:A\times
X\rightarrow\wp(A)$ is defined by $\alpha(a,x):=\\{\delta(a,x)\\}$ ($a\in
A,x\in X$). It is clear that $\alpha^{*}(a,w)=\\{\delta^{*}(a,w)\\}$ for all
$a\in A$ and $w\in X^{*}$, which implies the following facts.

###### Remark 3.1

For any DFA ${\mathcal{A}}$,
$DW({\mathcal{A}})=D_{1}({\mathcal{A}}^{{\mathbf{n}}{\mathbf{d}}})=D_{2}({\mathcal{A}}^{{\mathbf{n}}{\mathbf{d}}})=D_{3}({\mathcal{A}}^{{\mathbf{n}}{\mathbf{d}}})$.

Clearly, the directability of fuzzy automata may also be defined in several
ways. The definition suggested by Karthikeyan and Rajasekar [16] may be stated
as follows: $w\in X^{*}$ is a _directing word_ of an FFA $\mathcal{F}=(A,X,f)$
if there is a state $c\in A$ such that $f^{*}(a,w,c)>0$ (i.e.
$c\in{\mathcal{F}}(a,w)$) for every $a\in A$, and ${\mathcal{F}}$ is said to
be _directable_ if it has a directing word. Using these notions the authors
attempt to present some ideas and results appearing in [11] in a ‘fuzzified’
form. The discussion of these and related matters can be simplified by the
following reduction to nondeterministic automata.

Consider an FFA $\mathcal{F}=(A,X,f)$. A word $w=x_{1}\ldots x_{k}$
$(x_{1},\ldots,x_{k}\in X)$ is directing for ${\mathcal{F}}$ if and only if
there is a state $c\in A$ such that for every $a\in A$ there is a chain of
states $a=a_{0},a_{1},\ldots,a_{k}=c$ such that $f(a_{i-1},x_{i},a_{i})>0$ for
every $i\in{\mathbf{k}}$. The actual values of the degrees
$f(a_{i-1},x_{i},a_{i})$ do not matter as long as they are positive. Hence, we
could assign every positive transition the value 1 without changing the set of
directing words. This means that when we are interested just in directing
words, ${\mathcal{F}}$ may be replaced by the _associated NFA_
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}=(A,X,\alpha)$, where $\alpha$ is
defined by

$\alpha(a,x):=\\{b\in A\mid f(a,x,b)>0\\}\qquad(x\in X,a\in A).\vspace{-3pt}$

###### Example 3.2

Let ${\mathcal{F}}=(\\{a,b,c\\},\\{x,y\\},f)$ be the fuzzy automaton, where
the non-zero transitions are $f(a,x,b)=0.3$, $f(b,x,c)=0.4$, $f(c,x,b)=0.2$,
$f(c,x,c)=0.6$, $f(b,y,b)=0.5$ and $f(b,y,c)=0.1$. Then the transitions of
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ are given by $\alpha(a,x)=\\{b\\}$,
$\alpha(b,x)=\\{c\\}$, $\alpha(c,x)=\\{b,c\\}$, $\alpha(a,y)=\emptyset$,
$\alpha(b,y)=\\{b,c\\}$ and $\alpha(c,y)=\emptyset$.

It is easy to verify the following lemma by induction on $\mathrm{lg}(w)$.

###### Lemma 3.3

Let $\mathcal{F}=(A,X,f)$ be any FFA and
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}=(A,X,\alpha)$ be the associated NFA.
Then $\alpha^{*}(a,w)={\mathcal{F}}(a,w)$ for all $a\in A$ and $w\in X^{*}$.

Let us also note the following obvious fact.

###### Corollary 3.4

A fuzzy finite automaton ${\mathcal{F}}$ is complete if and only if the
associated NFA ${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ is complete.

###### Remark 3.5

A converse construction is possible, too, i.e., with any NFA
$\mathcal{N}=(A,X,\alpha)$, we may associate a related FFA
${\mathcal{N}}^{{\mathbf{f}}{\mathbf{z}}}=(A,X,f)$, where $f:A\times X\times
A\rightarrow[0,1]$ is defined by

$f(a,x,b)=\left\\{\begin{array}[]{cl}1,&\ \mbox{if }b\in\alpha(a,x)\\\ 0,&\
\mbox{if }b\notin\alpha(a,x).\vspace{-3pt}\end{array}\right.$

It is easy to see that ${\mathcal{N}}^{{\mathbf{f}}{\mathbf{z}}}$ is a crisp
FFA, and that

(a) ${\mathcal{N}}^{{\mathbf{f}}{\mathbf{z}}}$ is complete if and only if
${\mathcal{N}}$ is complete,

(b) ${\mathcal{N}}^{{\mathbf{f}}{\mathbf{z}}}(a,w)=\alpha^{*}(a,w)$ for all
$a\in A$ and $w\in X^{*}$, and

(c)
$({\mathcal{N}}^{{\mathbf{f}}{\mathbf{z}}})^{{\mathbf{n}}{\mathbf{d}}}={\mathcal{N}}$.
However,
$({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})^{{\mathbf{f}}{\mathbf{z}}}={\mathcal{F}}$
holds for an FFA ${\mathcal{F}}$ only in case ${\mathcal{F}}$ is crisp.

The above definitions of D1–, D2– and D3–directing words can be applied in a
natural way to fuzzy automata, too. For an FFA $\mathcal{F}=(A,X,f)$, let us
call a word $w\in X^{*}$

  * (D1’)

_D1–directing_ if $(\exists c\in A)(\forall a\in
A)({\mathcal{F}}(a,w)=\\{c\\})$,

  * (D2’)

_D2–directing_ if $(\forall a,b\in A)({\mathcal{F}}(a,w)={\mathcal{F}}(b,w))$,
and

  * (D3’)

_D3–directing_ if $(\exists c\in A)(\forall a\in A)(c\in{\mathcal{F}}(a,w))$.

For each $i=1,2,3$, the set of D$i$–directing words of ${\mathcal{F}}$ is
denoted by $D_{i}({\mathcal{F}})$, and ${\mathcal{F}}$ is said to be D$i$–
_directable_ if $D_{i}({\mathcal{F}})\neq\emptyset$.

The D3–directing words of a fuzzy automaton ${\mathcal{F}}$ are exactly the
directing words as defined in [16]. A pairwise comparison of conditions (Di)
and (Di’) ($i=1,2,3$) yields by Lemma 3.3 the following facts.

###### Proposition 3.6

For any FFA ${\mathcal{F}}$ and each $i=1,2,3$,
$D_{i}({\mathcal{F}})=D_{i}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})$, and
hence ${\mathcal{F}}$ is Di-directable if and only if
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$ is Di-directable.

Proposition 3.6 implies that all the known results concerning D$i$–directing
words of NFAs (cf. [3, 6, 7, 12, 14, 25], for example) apply to fuzzy
automata, too. For example, the following relations between the sets
$D_{1}({\mathcal{F}})$, $D_{2}({\mathcal{F}})$, and $D_{3}({\mathcal{F}})$,
for any fuzzy automaton ${\mathcal{F}}$, hold by Remark 3.2 of [12].

###### Remark 3.7

$D_{1}({\mathcal{F}})\subseteq D_{2}({\mathcal{F}})\cap D_{3}({\mathcal{F}})$
for any fuzzy automaton ${\mathcal{F}}$, and if ${\mathcal{F}}$ is complete,
then $D_{1}({\mathcal{F}})\subseteq D_{2}({\mathcal{F}})\subseteq
D_{3}({\mathcal{F}})$. Moreover, any one of the inclusions may be proper.

As noted in [11], for example, $X^{*}DW({\mathcal{A}})X^{*}=DW({\mathcal{A}})$
for any DFA ${\mathcal{A}}$, but the corresponding fact does not always hold
for the D3–directing words of a fuzzy automaton ${\mathcal{F}}$ as claimed in
[16]. In fact, neither $X^{*}D_{3}({\mathcal{F}})=D_{3}({\mathcal{F}})$ nor
$D_{3}({\mathcal{F}})X^{*}=D_{3}({\mathcal{F}})$ holds generally. For example,
the fuzzy automaton ${\mathcal{F}}$ of Example 3.2 has the D3–directing word
$xx$ while neither $yxx$ nor $xxy$ is in $D_{3}({\mathcal{F}})$. Remark 3.3 of
[12] yields the following facts.

###### Remark 3.8

$D_{2}({\mathcal{F}})X^{*}=D_{2}({\mathcal{F}})$ for any FFA ${\mathcal{F}}$.
If ${\mathcal{F}}$ is complete, then
$X^{*}D_{1}({\mathcal{F}})=D_{1}({\mathcal{F}})$,
$X^{*}D_{2}({\mathcal{F}})X^{*}=D_{2}({\mathcal{F}})$ and
$X^{*}D_{3}({\mathcal{F}})X^{*}=D_{3}({\mathcal{F}})$.

It is rather obvious that $D_{1}({\mathcal{F}})$, $D_{2}({\mathcal{F}})$ and
$D_{3}({\mathcal{F}})$ are regular languages for every FFA ${\mathcal{F}}$.
Although this also follows directly from Proposition 3.4 of [12], let us
present a simple proof formulated for FFAs.

###### Proposition 3.9

For any FFA ${\mathcal{F}}$, the languages $D_{1}({\mathcal{F}})$,
$D_{2}({\mathcal{F}})$ and $D_{3}({\mathcal{F}})$ are regular.

Proof. If $\mathcal{F}=(A,X,f)$ with $A=\\{a_{1},\ldots,a_{n}\\}$, let
$(B,X,\delta)$ be the DFA with
$B=\\{\\{{\mathcal{F}}(a_{1},u),\dots,{\mathcal{F}}(a_{n},u)\\}\mid u\in
X^{*}\\}$ and $\delta$ defined by

$\delta(\\{C_{1},\dots,C_{k}\\},x)=\\{{\mathcal{F}}(C_{1},x),\dots,{\mathcal{F}}(C_{k},x)\\}\vspace{-3pt}$

for all $\\{C_{1},\dots,C_{k}\\}\in B$ and $x\in X$. For
$b_{0}=\\{\\{a_{1}\\},\dots,\\{a_{n}\\}\\}$, we get
$\delta(b_{0},u)=\\{{\mathcal{F}}(a_{1},u),\dots,{\mathcal{F}}(a_{n},u)\\}$
for every $u\in X^{*}$. It is easy to see that, for each $i=1,2,3$,
$L({\mathbf{B}}_{i})=D_{i}({\mathcal{F}})$ for
${\mathbf{B}}_{i}=(B,X,\delta,b_{0},F_{i})$, when we choose
$F_{1}=\\{\\{\\{c\\}\\}\mid c\in A\\}\cap B$, $F_{2}=\\{\\{C\\}\mid C\subseteq
A\\}\cap B$, and $F_{3}=\\{\\{C_{1},\dots,C_{k}\\}\in B\mid C_{1}\cap\dots\cap
C_{k}\neq\emptyset\\}$. $\Box$

The construction used in the above proof is clearly effective if
${\mathcal{F}}$ is effectively given. This means that we may decide whether
${\mathcal{F}}$ is D1–, D2– or D3–directable. However, the decision method
suggested by this observation is feasible for very small FFAs only. We shall
now present a more effective way to decide the D3–directability of a complete
FFA.

Two states $a$ and $b$ of a DFA $\mathcal{A}=(A,X,\delta)$ are _merged_ by a
word $w\in X^{*}$ if $\delta^{*}(a,w)=\delta^{*}(b,w)$. The algorithm for
testing the directability of a DFA ${\mathcal{A}}$ presented in [11] is based
on the obvious fact that ${\mathcal{A}}$ is directable if and only if every
pair of states of ${\mathcal{A}}$ can be merged.

By the definition suggested in [16], two states $a$ and $b$ of an FFA
$\mathcal{F}=(A,X,f)$ are _merged_ by a word $w\in X^{*}$ if $f^{*}(a,w,c)>0$
and $f^{*}(b,w,c)>0$ for some $c\in A$. Theorem 4.1 of [16] claims that
${\mathcal{F}}$ is directable if and only if every pair of states can be
merged. The condition is trivially necessary, but the converse may fail if the
automaton is incomplete, and then the algorithm of [16], obtained from that of
[11] by replacing the Boolean matrix by a fuzzy matrix, may incorrectly
proclaim the automaton to be directable.

###### Example 3.10

Let ${\mathcal{F}}=(\\{a,b,c\\},\\{x,y,z\\},f)$ be the FFA in which
$f(a,x,a)$, $f(b,x,a)$, $f(b,y,b)$, $f(c,y,b)$, $f(a,z,c)$ and $f(c,z,c)$ are
the transitions with non-zero degrees. Clearly, $a$ and $b$ are merged by $x$,
$b$ and $c$ by $y$, and $a$ and $c$ by $z$, but
$D_{3}({\mathcal{F}})=\emptyset$ since
$f^{*}(a,yw,d)=f^{*}(b,zw,d)=f^{*}(c,xw,d)=0$ for all $w\in X^{*}$ and $d\in
A$.

However, the algorithm of [11] can be used, almost without any change, for
testing a complete FFA for D3–directability.

In [12] a word $w\in X^{*}$ was defined to _D3–merge_ two states $a,b\in A$ of
an NFA $\mathcal{N}=(A,X,\alpha)$ if
$\alpha^{*}(a,w)\cap\alpha^{*}(b,w)\neq\emptyset$. Let us say that $w$
_D3–merges_ two states $a,b\in A$ of an FFA ${\mathcal{F}}$ if
${\mathcal{F}}(a,w)\cap{\mathcal{F}}(b,w)\neq\emptyset$. A word merges, in the
sense of [16], two states if and only if it D3–merges them.

###### Lemma 3.11

A word D3–merges two states of an FFA ${\mathcal{F}}$ if and only if it
D3–merges them in the associated NFA
${\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}$. Hence a complete FFA is
D3–directable if and only if every pair of its states has a D3–merging word.

Proof. The first assertion is valid by Lemma 3.3. The rest of the lemma
follows then from Lemma 5.4 of [12] which expresses the corresponding fact for
NFAs. $\Box$

For any $k\geq 0$, two states $a,b\in A$ of an FFA $\mathcal{F}=(A,X,f)$ are
said to be _D3 $k$-mergeable_ if they are D3–merged by a word of length $\leq
k$. We denote the D3 $k$-mergeability relation of ${\mathcal{F}}$ by $\mu(k)$,
and let $\mu:=\bigcup_{k\geq 0}\mu(k)$.

It is easy to verify the following proposition that justifies the algorithm to
be presented. It corresponds exactly to Proposition 4.1 of [11].

###### Proposition 3.12

Let $\mathcal{F}=(A,X,f)$ be a complete FFA.

  * (a)

${\mathcal{F}}$ is D3–directable if and only if $\mu=A\times A$.

  * (b)

The relations $\mu(k)$ and $\mu$ are reflexive and symmetric.

  * (c)

$\mu(0)=\Delta_{A}$, and $\mu(k)=\mu(k-1)\cup\\\ \\{(a,b)\mid(\exists x\in
X)[({\mathcal{F}}(a,x)\times{\mathcal{F}}(b,x))\cap\mu(k-1)\neq\emptyset]\\}$
for $k\geq 1$.

  * (d)

If $\mu(k)=\mu(k-1)$ for some $k\geq 1$, then $\mu(k)=\mu$.

  * (e)

$\Delta_{A}=\mu(0)\subset\mu(1)\subset\ldots\subset\mu(k)=\mu$ for some
$k\leq{n\choose 2}$, where $n=|A|$.

Let $\mathcal{F}=(A,X,f)$ be an $n$-state complete FFA with
$A=\\{1,\ldots,n\\}$. The algorithm implicitly computes the relations
$\mu(0),\mu(1),\ldots$ until $\mu(k-1)=\mu(k)$ for some $k\geq 1$. It employs
a Boolean $n\times n$-matrix $M$ and a list $NewPair$ of pairs of states. The
meaning of $M[i,j]=1$ is that states $i$ and $j$ are known to be D3–mergeable.
It suffices to consider the entries $M[i,j]$ with $1\leq i<j\leq n$. A pair
$(i,j)$ appears on the list $NewPair$ if it is known to be D3–mergeable but
this fact has not yet been utilized for finding new D3–mergeable pairs. We
also use the _inverted transition table_
${\mathbf{I}}=({\mathbf{I}}[a,x])_{a\in A,x\in X}$, where
${\mathbf{I}}[a,x]:=\\{i\in A\mid a\in{\mathcal{F}}(i,x)\\}$ for all $a\in A$
and $x\in X$. The steps of the algorithm are as follows:

1\. Set $M[i,j]:=0$ for $1\leq i<j\leq n$, $NewPair:=\varepsilon$ (empty
list), and compute ${\mathbf{I}}$.

2\. Find all pairs $(a,x)\in A\times X$ for which $|{\mathbf{I}}[a,x]|>1$. For
each such pair $(a,x)$ consider every pair $i,j\in{\mathbf{I}}[a,x]$ with
$i<j$. If $M[i,j]=0$, let $M[i,j]:=1$ and append $(i,j)$ to $NewPair$.

3\. Until $NewPair=\varepsilon$ do the following. Delete the first pair, say
$(a,b)$, from $NewPair$. For each $x\in X$, find all pairs $(i,j)$ with $i<j$
such that $i\in{\mathbf{I}}[a,x]$ and $j\in{\mathbf{I}}[b,x])$, or
$j\in{\mathbf{I}}[a,x]$ and $i\in{\mathbf{I}}[b,x])$. If $M[i,j]=0$, let
$M[i,j]:=1$ and append $(i,j)$ to $NewPair$.

4\. ${\mathcal{F}}$ is D3–directable if and only if $M[i,j]=1$ whenever $1\leq
i<j\leq n$.

Quite the same way as in [11], one can show that the time bound for the
algorithm is ${\mathcal{O}}(m\cdot n^{2})$, where $m=|X|$ and $n=|A|$.

It appears unlikely that anything like the above algorithm exists for D1– or
D2–directability as there does not seem to be any useful notions of D1– or
D2–merging words. Furthermore, while the shortest D3–directing word of a
complete D3–directable $n$-state NFA is at most of length of order
$\mathcal{O}(n^{3})$ (cf. Proposition 5.3 of [12]), no polynomial upper bounds
exist for shortest D1– and D2–directing words (cf. [3, 6, 7, 12]).

##  4 Directability with degrees

We shall now introduce three new types of directing words for FFAs that are
analogous to the D1–, D2– and D3–directing words but depend more on the
transition degrees $f(a,x,b)$ of the automaton.

For a given FFA $\mathcal{F}=(A,X,f)$, we say that a word $w\in X^{*}$ is

  * (DD1)

_DD1–directing_ if $(\exists c\in A)(\exists r\in(0,1])(\forall a\in
A)({\mathcal{F}}_{a,w}=\\{c/r\\})$,

  * (DD2)

_DD2–directing_ if $(\forall a,b\in
A)({\mathcal{F}}_{a,w}={\mathcal{F}}_{b,w})$, and

  * (DD3)

_DD3–directing_ if $(\exists c\in A)(\forall a\in
A)({\mathcal{F}}_{a,w}(c)=\max\\{{\mathcal{F}}_{a,w}(b)\mid b\in A\\}>0)$.

For each $i=1,2,3$, the set of DD$i$–directing words of ${\mathcal{F}}$ is
denoted by $D\\!D_{i}({\mathcal{F}})$, and ${\mathcal{F}}$ is said to be _DD
$i$–directable_ if $D\\!D_{i}({\mathcal{F}})\neq\emptyset$.

If condition (DD1) holds, then for every state $a\in A$, $c$ is the only state
reachable from $a$ by the input word $w$, and its reachability degree
${\mathcal{F}}_{a,w}(c)$ has the same value $r>0$ for every $a$. That $w$
satisfies (DD2) means that the fuzzy set ${\mathcal{F}}_{a,w}$ of states
reached from a given state $a$ by input $w$ is the same for every $a$, i.e.,
$f^{*}(a,w,c)=f^{*}(b,w,c)$ for all $a,b,c\in A$. Finally, condition (DD3)
means that there is a state $c$ which has the maximal reachability degree
${\mathcal{F}}_{a,w}(c)>0$ by the input $w$ from any state $a\in A$.

Let us see how these notions are related to each other and the previously
considered types of directing words of fuzzy automata.

###### Proposition 4.1

Let $\mathcal{F}=(A,X,f)$ be any FFA.

  * (a)

$D\\!D_{1}({\mathcal{F}})\subseteq D_{1}({\mathcal{F}})$,

  * (b)

$D\\!D_{1}({\mathcal{F}})\subseteq D\\!D_{2}({\mathcal{F}})\subseteq
D_{2}({\mathcal{F}})$,

  * (c)

$D\\!D_{1}({\mathcal{F}})\subseteq D\\!D_{3}({\mathcal{F}})\subseteq
D_{3}({\mathcal{F}})$, and

  * (d)

$D\\!D_{1}({\mathcal{F}})\subseteq D\\!D_{2}({\mathcal{F}})\cap
D\\!D_{3}({\mathcal{F}})$.

Any one of the inclusions may be proper.

Proof. The inclusions follow rather easily from the definitions. Let us prove
statements (b) and (d).

If $w\in D\\!D_{1}({\mathcal{F}})$, and (DD1) holds for $c\in A$ and
$r\in(0,1]$, then ${\mathcal{F}}_{a,w}=\\{c/r\\}={\mathcal{F}}_{b,w}$ for all
$a,b\in A$, and thus $w\in D\\!D_{2}({\mathcal{F}})$.

If $w\in D\\!D_{2}({\mathcal{F}})$, then
${\mathcal{F}}(a,w)=\mathrm{supp}({\mathcal{F}}_{a,w})=\mathrm{supp}({\mathcal{F}}_{w,b})={\mathcal{F}}(b,w)$
for all $a,b\in A$, and hence $w\in D_{2}({\mathcal{F}})$.

To show that the inclusion $D\\!D_{1}({\mathcal{F}})\subseteq
D\\!D_{2}({\mathcal{F}})$ may be proper, we consider the FFA
$\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$, $X=\\{x\\}$, and $f$ is defined by
$f(a,x,a)=f(b,x,a)=f(a,x,b)=f(b,x,b)=1$. The word $x$ does not belong to
$D\\!D_{1}({\mathcal{F}})$ because ${\mathcal{F}}_{a,x}=\\{a/1,b/1\\}$. On the
other hand, $x\in D\\!D_{2}({\mathcal{F}})$ because
${\mathcal{F}}_{a,x}=\\{a/1,b/1\\}={\mathcal{F}}_{b,x}$.

The inclusion $D\\!D_{2}({\mathcal{F}})\subseteq D_{2}({\mathcal{F}})$ is
proper for ${\mathcal{F}}=(\\{a,b\\},\\{x\\},f)$, if $f$ is defined by
$f(a,x,b)=0.1$ and $f(b,x,b)=0.2$. Now $x\notin D\\!D_{2}({\mathcal{F}})$
because ${\mathcal{F}}_{a,x}(b)=0.1$ while ${\mathcal{F}}_{b,x}(b)=0.2$. On
the other hand, $x\in D_{2}({\mathcal{F}})$ since
${\mathcal{F}}(a,x)=\\{b\\}={\mathcal{F}}(b,x)$.

The inclusion relation in (d) follows from (b) and (c). That it may be proper,
is seen by considering the first FFA defined above in this proof; the word $x$
belongs to $D\\!D_{2}({\mathcal{F}})\cap D\\!D_{3}({\mathcal{F}})$, but not to
$D\\!D_{1}({\mathcal{F}})$ $\Box$

Let us say that an FFA $\mathcal{F}=(A,X,f)$ is _crisp_ if
$f(a,x,b)\in\\{0,1\\}$ for all $a,b\in A$ and $x\in X$. It is easy to see that
if ${\mathcal{F}}$ is crisp, then for all $a,b\in A$ and $w\in X^{*}$,

(1) $f^{*}(a,w,b)\in\\{0,1\\}$, and

(2) ${\mathcal{F}}_{a,w}=\\{a_{1}/1,\ldots,a_{k}/1\\}$, where
$\\{a_{1},\ldots,a_{k}\\}={\mathcal{F}}(a,w)$.

From (2) we get the following facts.

###### Remark 4.2

If $\mathcal{F}=(A,X,f)$ is a crisp FFA, then
$D\\!D_{1}({\mathcal{F}})=D_{1}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})=D_{1}({\mathcal{F}})$,
$D\\!D_{2}({\mathcal{F}})=D_{2}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})=D_{2}({\mathcal{F}})$
and
$D\\!D_{3}({\mathcal{F}})=D_{3}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})=D_{3}({\mathcal{F}})$.

Proof. Let us verify the first pair of equalities. For any $w\in X^{*}$,

$\displaystyle w\in D\\!D_{1}({\mathcal{F}})$
$\displaystyle\Leftrightarrow(\exists c\in A)(\exists r\in(0,1])(\forall a\in
A){\mathcal{F}}_{a,w}=\\{c/r\\}\vspace{-3pt}$
$\displaystyle\Leftrightarrow(\exists c\in A)(\forall a\in
A){\mathcal{F}}_{a,w}=\\{c/1\\}\vspace{-3pt}$
$\displaystyle\Leftrightarrow(\exists c\in A)(\forall a\in
A){\mathcal{F}}(a,w)=\\{c\\}\vspace{-3pt}$ $\displaystyle\Leftrightarrow w\in
D_{1}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}}).\vspace{-3pt}$

Hence,
$D\\!D_{1}({\mathcal{F}})=D_{1}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})$,
and $D_{1}({\mathcal{F}}^{{\mathbf{n}}{\mathbf{d}}})=D_{1}({\mathcal{F}})$ by
Proposition 3.6. The other two pairs of equalities have similar
straightforward proofs. $\Box$

When dealing with fuzzy finite automata it may be convenient to use their
matrix representations. For any $m,n\geq 1$, a _fuzzy $m\times n$-matrix_ is
an $m\times n$-array $(r_{ij})$ in which $r_{ij}\in[0,1]$ for all
$i\in{\mathbf{m}}$ and $j\in{\mathbf{n}}$. The _product_ of a fuzzy $m\times
k$-matrix $R=(r_{ij})$ and a fuzzy $k\times n$-matrix $S=(s_{ij})$ is the
fuzzy $m\times n$-matrix $RS=(t_{ij})$, where

$t_{ij}=(r_{i1}\land s_{1j})\vee\ldots\vee(r_{ik}\land
s_{kj})\qquad(i\in{\mathbf{m}},j\in{\mathbf{n}}).\vspace{-3pt}$

Let $\mathcal{F}=(A,X,f)$ be an $n$-state FFA with
$A=\\{a_{1},\ldots,a_{n}\\}$. With any word $w\in X^{*}$, we associate its
fuzzy $n\times n$ _transition matrix_

$M^{\mathcal{F}}_{w}=M_{w}=(r_{ij}),\text{ where
}r_{ij}=f^{*}(a_{i},w,a_{j})\qquad(i,j\in{\mathbf{n}}).$

For any words $u,v\in X^{*}$, $M_{uv}=M_{u}M_{v}$ because

$f(a_{i},uv,a_{j})=\max\\{f^{*}(a_{i},u,a_{k})\land f^{*}(a_{k},v,a_{j})\mid
k\in{\mathbf{n}}\\}\qquad(i,j\in{\mathbf{n}}).\vspace{-3pt}$

For any $w\in X^{*}$ and $i\in{\mathbf{n}}$, the $i^{th}$ row
$(r_{i1}\,r_{i2}\,\ldots\,r_{in})$ of $M_{w}$ represents the fuzzy set
${\mathcal{F}}_{a_{i},w}$, i.e.,

$r_{i1}={\mathcal{F}}_{a_{i},w}(a_{1}),\,r_{i2}={\mathcal{F}}_{a_{i},w}(a_{2}),\ldots,r_{in}={\mathcal{F}}_{a_{i},w}(a_{n})\qquad(i\in{\mathbf{n}})\vspace{-3pt}$

By this observation, one may deduce from the matrix $M_{w}$ whether the word
$w$ is DD1–, DD2– or DD3–directing, and this will be used in the proof of the
following proposition.

###### Proposition 4.3

For any FFA $\mathcal{F}=(A,X,f)$, the languages $D\\!D_{1}({\mathcal{F}})$,
$D\\!D_{2}({\mathcal{F}})$ and $D\\!D_{3}({\mathcal{F}})$ are recognizable.

Proof. Let $A=\\{a_{1},\ldots,a_{n}\\}$. The set $B:=\\{M_{w}\mid w\in
X^{*}\\}$ is finite because all the matrix entries belong to the finite set
$\\{f(a_{i},x,a_{j})\mid i,j\in{\mathbf{n}},x\in X\\}\cup\\{1\\}$. To see
this, it suffices to notice that no new elements are introduced when matrices
are multiplied as the only operations used are the join $\max(r,s)$ and meet
$\min(r,s)$ in the chain $([0,1],\leq)$.

Let $(B,X,\delta)$ be the DFA for which $\delta:B\times X\rightarrow B$ is
defined by $\delta(M_{w},x)=M_{wx}$ ($w\in X^{*},x\in X$). It is easy to show
that $\delta^{*}(M_{\varepsilon},w)=M_{w}$ for every $w\in X^{*}$. From this
observation, it follows that for each $i=1,2,3$, we get a DFR
${\mathbf{B}}_{i}=(B,X,\delta,M_{\varepsilon},F_{i})$ recognizing
$D\\!D_{i}({\mathcal{F}})$ by the following choices of the sets $F_{i}$ of
final states.

  1. 1.

$M_{w}\in F_{1}$ if and only if for some $j\in{\mathbf{n}}$ and $r\in(0,1]$,
$r_{1j}=\ldots=r_{nj}=r$ and $r_{ik}=0$ for all $i,k\in{\mathbf{n}}$ with
$k\neq j$.

  2. 2.

$M_{w}\in F_{2}$ if and only if all the rows in $M_{w}$ are identical.

  3. 3.

$M_{w}\in F_{3}$ if and only if for some $j\in{\mathbf{n}}$, in every row, the
$j^{th}$ element is maximal and positive. $\Box$

In Remark 3.8 we noted some equalities satisfied by the
$D_{i}({\mathcal{F}})$-languages, but not all of them hold for the
$D\\!D_{i}({\mathcal{F}})$-languages. For example, let
${\mathcal{F}}=(\\{a,b\\},\\{x,y\\},f)$ be the complete FFA in which the
nonzero transitions are $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$ and $f(a,y,a)=0.5$.
Then $x\in D\\!D_{1}({\mathcal{F}})$ because
${\mathcal{F}}_{a,x}={\mathcal{F}}_{b,x}=\\{b/1\\}$, but $yx\notin
D\\!D_{1}({\mathcal{F}})$ since ${\mathcal{F}}_{a,yx}=\\{b/0.5\\}$ while
${\mathcal{F}}_{b,yx}=\\{b/1\\}$. Hence, $X^{*}D\\!D_{1}({\mathcal{F}})\neq
D\\!D_{1}({\mathcal{F}})$. Similarly, $X^{*}D\\!D_{2}({\mathcal{F}})\neq
D\\!D_{2}({\mathcal{F}})$ because $x$ is a D2–directing word of
${\mathcal{F}}$, but $yx$ is not. However, the equality
$X^{*}D\\!D_{1}({\mathcal{F}})=D\\!D_{1}({\mathcal{F}})$, for example, holds
if we replace the completeness of an FFA by the stronger property of
“normality”.

Let us say that an FFA $\mathcal{F}=(A,X,f)$ is _normal_ if for every pair
$a\in A,\,x\in X$, there is a state $b\in A$ for which $f(a,x,b)=1$, i.e.,
${\mathcal{F}}_{a,x}$ is a normal fuzzy set.

###### Lemma 4.4

If $\mathcal{F}=(A,X,f)$ is a normal FFA, then for all $a\in A$ and $w\in
X^{*}$, there is a state $b\in A$ such that $f^{*}(a,w,b)=1$. Hence, if
${\mathcal{F}}$ is normal and $w\in D\\!D_{3}({\mathcal{F}})$, then there is a
$c\in A$ such that $f^{*}(a,w,c)=1$ for every $a\in A$.

###### Proposition 4.5

For any FFA $\mathcal{F}=(A,X,f)$,

  * (a)

$D\\!D_{2}({\mathcal{F}})X^{*}=D\\!D_{2}({\mathcal{F}})$.

If ${\mathcal{F}}$ is normal, then we also have

  * (b)

$X^{*}D\\!D_{1}({\mathcal{F}})=D\\!D_{1}({\mathcal{F}})$,

  * (c)

$X^{*}D\\!D_{2}({\mathcal{F}})X^{*}=D\\!D_{2}({\mathcal{F}})$, and

  * (d)

$X^{*}D\\!D_{3}({\mathcal{F}})X^{*}=D\\!D_{3}({\mathcal{F}})$.

Proof. To prove (a), consider any words $w\in D\\!D_{2}({\mathcal{F}})$ and
$u\in X^{*}$. For all $a,b,c\in A$,

$\displaystyle{\mathcal{F}}_{a,wu}(c)$ $\displaystyle=\max\\{f^{*}(a,w,d)\land
f^{*}(d,u,c)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle=\max\\{f^{*}(b,w,d)\land f^{*}(d,u,c)\mid d\in
A\\}={\mathcal{F}}_{b,wu}(c),\vspace{-3pt}$

which shows that $D\\!D_{2}({\mathcal{F}})X^{*}\subseteq
D\\!D_{2}({\mathcal{F}})$. The converse inclusion is obvious.

Assume now that ${\mathcal{F}}$ is normal. To prove (b), consider any $w\in
D\\!D_{1}({\mathcal{F}})$, and let $c\in A$ and $r\in(0,1]$ be such that
${\mathcal{F}}_{a,w}=\\{c/r\\}$ for every $a\in A$. Take any $u\in X^{*}$ and
$a\in A$. By Lemma 4.4, there is a $b\in A$ such that $f^{*}(a,u,b)=1$, and
therefore

$\displaystyle f^{*}(a,uw,c)$ $\displaystyle=\max\\{f^{*}(a,u,d)\land
f^{*}(d,w,c)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle=\max\\{f^{*}(a,u,d)\mid d\in A\\}\land r\vspace{-3pt}$
$\displaystyle=1\land r=r,\vspace{-3pt}$

where we used the fact that $f^{*}(d,w,c)=r$ for every $d\in A$. On the other
hand, if $c^{\prime}\in A$, $c^{\prime}\neq c$, then for every $a\in A$

$\displaystyle f^{*}(a,uw,c^{\prime})$ $\displaystyle=\max\\{f^{*}(a,u,d)\land
f^{*}(d,w,c^{\prime})\mid d\in A\\}\vspace{-3pt}$
$\displaystyle=\max\\{f^{*}(a,u,d)\land 0\mid d\in
A\\}\vspace{-3pt}=0.\vspace{-3pt}$

This shows that $uw\in D\\!D_{1}({\mathcal{F}})$, and hence
$X^{*}D\\!D_{1}({\mathcal{F}})\subseteq D\\!D_{1}({\mathcal{F}})$.

As we already have $D\\!D_{2}({\mathcal{F}})X^{*}=D\\!D_{2}({\mathcal{F}})$,
we get (c) by showing that $X^{*}D\\!D_{2}({\mathcal{F}})\subseteq
D\\!D_{2}({\mathcal{F}})$. Let $u\in X^{*}$ and $w\in
D\\!D_{2}({\mathcal{F}})$, and consider any $a,b,c\in A$. Let
$a^{\prime},b^{\prime}\in A$ be such that
$f^{*}(a,u,a^{\prime})=f^{*}(b,u,b^{\prime})=1$. Then

$\displaystyle f^{*}(a,uw,c)$ $\displaystyle=\max\\{f^{*}(a,u,d)\land
f^{*}(d,w,c)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle=f^{*}(a,u,a^{\prime})\land f^{*}(a^{\prime},w,c)\vspace{-3pt}$
$\displaystyle=1\land f^{*}(a^{\prime},w,c)=1\land
f^{*}(b^{\prime},w,c)\vspace{-3pt}$ $\displaystyle=\max\\{f^{*}(b,u,d)\land
f^{*}(d,w,c)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle=f^{*}(b,uw,c),\vspace{-3pt}$

where we also used the fact that
$f^{*}(a^{\prime},w,c)=f^{*}(d,w,c)=f^{*}(b^{\prime},w,c)$ for every $d\in A$.
Thus we have shown that $uw\in D\\!D_{2}({\mathcal{F}})$.

Finally, to prove (d), consider any $u\in X^{*}$ and $w\in
D\\!D_{3}({\mathcal{F}})$. Let $c\in A$ be a state such that, for every $a\in
A$, $f^{*}(a,w,c)>0$ and $f^{*}(a,w,b)\leq f^{*}(a,w,c)$ for every $b\in A$.
If $c^{\prime}\in A$ is a state such that $f^{*}(c,u,c^{\prime})=1$, then for
any $a\in A$,

$\displaystyle f^{*}(a,wu,c^{\prime})$ $\displaystyle=\max\\{f^{*}(a,w,d)\land
f^{*}(d,u,c^{\prime})\mid d\in A\\}\vspace{-3pt}$ $\displaystyle\geq
f^{*}(a,w,c)\land f^{*}(c,u,c^{\prime})\vspace{-3pt}$
$\displaystyle=f^{*}(a,w,c)>0.$

Moreover, for any $b\in A$,

$\displaystyle f^{*}(a,wu,b)$ $\displaystyle=\max\\{f^{*}(a,w,d)\land
f^{*}(d,u,b)\mid d\in A\\}\vspace{-3pt}$ $\displaystyle\leq
f^{*}(a,w,c)\land\max\\{f^{*}(d,u,b)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle\leq f^{*}(a,w,c)=f^{*}(a,w,c)\land
f^{*}(c,u,c^{\prime})\vspace{-3pt}$ $\displaystyle\leq
f^{*}(a,wu,c^{\prime}),$

where we used the fact that $f(a,w,d)\leq f(a,w,c)$ for every $d\in A$, and
thus $wu\in D\\!D_{3}({\mathcal{F}})$. The converse inclusion
$D\\!D_{3}({\mathcal{F}})\subseteq D\\!D_{3}({\mathcal{F}})X^{*}$ holds
trivially. To complete the proof of (d), we show that
$X^{*}D\\!D_{3}({\mathcal{F}})\subseteq D\\!D_{3}({\mathcal{F}})$. Let $w\in
D\\!D_{3}({\mathcal{F}})$, $c\in A$ and $u\in X^{*}$ be as above. Consider any
$a\in A$ and let $a^{\prime}\in A$ be a state for which
$f^{*}(a,u,a^{\prime})=1$. Then

$\displaystyle f^{*}(a,uw,c)$ $\displaystyle=\max\\{f^{*}(a,u,d)\land
f^{*}(d,w,c)\mid d\in A\\}\vspace{-3pt}$ $\displaystyle\geq
f^{*}(a,u,a^{\prime})\land
f^{*}(a^{\prime},w,c)=f^{*}(a^{\prime},w,c)>0\vspace{-3pt}$

Moreover, for any $b\in A$,

$\displaystyle f^{*}(a,uw,b)$ $\displaystyle=\max\\{f^{*}(a,u,d)\land
f^{*}(d,w,b)\mid d\in A\\}\vspace{-3pt}$
$\displaystyle\leq\max\\{f^{*}(a,u,d)\land f^{*}(d,w,c)\mid d\in
A\\}=f^{*}(a,uw,c),\vspace{-3pt}$

and hence $uw\in D\\!D_{3}({\mathcal{F}})$. $\Box$

It is easy to see that if $L=RX^{*}(\subseteq X^{*})$, where $R$ is a nonempty
regular language, then any minimal DFR ${\mathbf{A}}=(A,X,\delta,a_{0},F)$ of
$L$ has exactly one final state, and this state $d$ is a _trap state_ , i.e.,
$\delta(d,x)=d$ for every $x\in X$. Hence, Proposition 4.5 yields the
following facts.

###### Corollary 4.6

If an FFA $\mathcal{F}=(A,X,f)$ is $D\\!D2$-directable, then any minimal DFR
recognizing $D\\!D_{2}({\mathcal{F}})$ has exactly one final state, and this
is a trap state. If ${\mathcal{F}}$ is normal and D3–directable, then any
minimal DFR recognizing $D\\!D_{3}({\mathcal{F}})$ has exactly one final
state, and this is a trap state.

##  5 Families of sets of $DDi$-directing words

Let us now consider the families of languages $D\\!D_{i}({\mathcal{F}})$
formed by the DD$i$–directing words of DD$i$–directable FFAs. In [9] Imreh and
Ito studied the families of the sets $D_{i}({\mathcal{N}})$ of D$i$–directing
words of $Di$-directable NFAs. Their results, also presented in [13], apply
directly to fuzzy automata, too.

Let ${\mathcal{L}}=\\{{\mathcal{L}}(X)\\}_{X}$ and
${\mathcal{K}}=\\{{\mathcal{K}}(X)\\}_{X}$ be families of languages.
${\mathcal{K}}$ is a _subfamily_ of ${\mathcal{L}}$,
${\mathcal{K}}\subseteq{\mathcal{L}}$ in symbols, if
${\mathcal{K}}(X)\subseteq{\mathcal{L}}(X)$ for every alphabet $X$. If
${\mathcal{K}}\subseteq{\mathcal{L}}$, but ${\mathcal{K}}\neq{\mathcal{L}}$,
then ${\mathcal{K}}$ is a _proper subfamily_ of ${\mathcal{L}}$ and we write
${\mathcal{K}}\subset{\mathcal{L}}$. The _intersection_ of ${\mathcal{K}}$ and
${\mathcal{L}}$ is the family
${\mathcal{K}}\cap{\mathcal{L}}:=\\{{\mathcal{K}}(X)\cap{\mathcal{L}}(X)\\}_{X}$.
The families ${\mathcal{K}}$ and ${\mathcal{L}}$ are _incomparable_ if neither
${\mathcal{K}}\subseteq{\mathcal{L}}$ nor
${\mathcal{L}}\subseteq{\mathcal{K}}$ holds. This is expressed by
${\mathcal{K}}\parallel{\mathcal{L}}$.

For each $i\in\mathbf{3}$, let
$\mathcal{D\\!D}_{i}=\\{\mathcal{D\\!D}_{i}(X)\\}_{X}$ be the family of the
sets $D\\!D_{i}({\mathcal{F}})$ of DD$i$–directing words of DD$i$–directable
FFAs. Similarly, let $n\mathcal{D\\!D}_{i}=\\{n\mathcal{D\\!D}_{i}(X)\\}_{X}$
be the family of the sets $D\\!D_{i}({\mathcal{F}})$, where ${\mathcal{F}}$ is
a DD$i$–directable normal FFA. Furthermore, let
$\mathcal{DW}=\\{\mathcal{DW}(X)\\}_{X}$ be the family of the sets
$DW({\mathcal{A}})$ of directing words of directable DFAs. Note that any
language belonging to $\mathcal{D\\!D}_{1}(X)$, $\mathcal{D\\!D}_{2}(X)$,
$\mathcal{D\\!D}_{3}(X)$ or $\mathcal{DW}(X)$ for some $X$ is, by definition,
nonempty.

The following facts are easily verified.

###### Lemma 5.1

For any DFA $\mathcal{A}=(A,X,\delta)$, the FFA
${\mathcal{A}}^{{\mathbf{f}}{\mathbf{z}}}=(A,X,f)$ is normal, and for all
$a,b\in A$ and $w\in X^{*}$,

$f^{*}(a,w,b)=\left\\{\begin{array}[]{cl}1,&\ \mbox{if
}\delta^{*}(a,w)=b\,;\\\ 0,&\
\mbox{otherwise}.\vspace{-3pt}\end{array}\right.$

Furthermore,
$D\\!D_{1}({\mathcal{A}}^{{\mathbf{f}}{\mathbf{z}}})=D\\!D_{2}({\mathcal{A}}^{{\mathbf{f}}{\mathbf{z}}})=D\\!D_{3}({\mathcal{A}}^{{\mathbf{f}}{\mathbf{z}}})=DW({\mathcal{A}})$.

###### Corollary 5.2

$\mathcal{DW}\subseteq\,n\mathcal{D\\!D}_{1}\cap n\mathcal{D\\!D}_{2}\cap
n\mathcal{D\\!D}_{3}$.

It is clear that $X^{*}DW({\mathcal{A}})X^{*}=DW({\mathcal{A}})$ for any DFA
${\mathcal{A}}$, and in [9] it was shown that this is a characteristic
property of the languages $DW({\mathcal{A}})$:

###### Proposition 5.3

[9] A language $L\subseteq X^{*}$ belongs to $\mathcal{DW}(X)$ if and only if
$L\in Rec(X)$, $L\neq\emptyset$ and $X^{*}LX^{*}=L$.

###### Proposition 5.4

$\mathcal{DW}\subset\,\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}$.

Proof. The inclusion holds by Corollary 5.2 (naturally
$n\mathcal{D\\!D}_{i}\subseteq\mathcal{D\\!D}_{i}$ for each $i$). Let
$\mathcal{F}=(A,X,f)$ be the FFA in which $A=\\{a,b\\}$, $X=\\{x,y\\}$. and
$f$ is given by $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$. Clearly,
${\mathcal{F}}_{a,xu}={\mathcal{F}}_{b,xu}=\\{b/1\\}$ and
${\mathcal{F}}_{a,yu}=\emptyset$ for every $u\in X^{*}$. Thus
$\mathcal{D\\!D}_{1}({\mathcal{F}})=\mathcal{D\\!D}_{2}({\mathcal{F}})=\mathcal{D\\!D}_{3}({\mathcal{F}})=xX^{*}$.
Since $xX^{*}\notin\mathcal{DW}(X)$, the claimed inclusion is proper. $\Box$

###### Proposition 5.5

  * (a)

$\mathcal{DW}\subset n\mathcal{D\\!D}_{1}\subset\mathcal{D\\!D}_{1}$.

  * (b)

$\mathcal{DW}=n\mathcal{D\\!D}_{2}\subset\mathcal{D\\!D}_{2}$.

  * (c)

$\mathcal{DW}=n\mathcal{D\\!D}_{3}\subset\mathcal{D\\!D}_{3}$.

Proof. The relations $\mathcal{DW}\subseteq n\mathcal{D\\!D}_{i}$ ($i=1,2,3$)
hold by Corollary 5.2. Let us prove separately the remaining parts of the
three statements.

To prove $\mathcal{DW}\subset n\mathcal{D\\!D}_{1}$, let us consider the
normal FFA $\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$, $X=\\{x,y\\}$, and $f$
is given by $f(a,x,b)=f(a,y,a)=f(b,x,b)=f(b,y,a)=f(b,y,b)=1$. Clearly,
$DD_{1}({\mathcal{F}})$ is the language $X^{*}x$ which does not belong to
$\mathcal{DW}(X)$.

That the inclusion $n\mathcal{D\\!D}_{1}\subset\mathcal{D\\!D}_{1}$ is proper,
is seen by considering the FFA $\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$,
$X=\\{x,y\\}$, and $f$ is given by $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$ and
$f(a,y,a)=0.5$. Obviously, $DD_{1}({\mathcal{F}})=xX^{*}$, but $xX^{*}\notin
n\mathcal{D\\!D}_{1}(X)$ by Proposition 4.5 (b).

(b) To prove that $\mathcal{DW}=n\mathcal{D\\!D}_{2}$, it suffices to show
that $n\mathcal{D\\!D}_{2}\subseteq\mathcal{DW}$. If $L\in
n\mathcal{D\\!D}_{2}(X)$, then $L\neq\emptyset$ and $L\in Rec(X)$. Moreover,
$X^{*}LX^{*}=L$ by Proposition 4.5 (c), and thus $L\in\mathcal{DW}(X)$

Let $\mathcal{F}=(A,X,f)$ be the FFA, where $A=\\{a,b\\}$, $X=\\{x,y\\}$ and
$f$ is given by $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$. By Proposition 4.5 (c),
$DD_{2}({\mathcal{F}})=xX^{*}$ is not in $n\mathcal{D\\!D}_{2}(X)$. Hence
inclusion $n\mathcal{D\\!D}_{2}\subseteq\mathcal{D\\!D}_{2}$ is proper.

(c) That $\mathcal{DW}=n\mathcal{D\\!D}_{3}$ can be shown similarly as
$\mathcal{DW}=n\mathcal{D\\!D}_{2}$ above. To prove
$n\mathcal{D\\!D}_{3}\subset\mathcal{D\\!D}_{3}$, we consider again the FFA
${\mathcal{F}}$ defined in part (b) above: $DD_{3}({\mathcal{F}}^{*})=xX^{*}$
is not in $n\mathcal{D\\!D}_{3}(X)$. $\Box$

###### Proposition 5.6

$\mathcal{DW}=n\mathcal{D\\!D}_{1}\cap n\mathcal{D\\!D}_{2}\cap
n\mathcal{D\\!D}_{3}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{3}.$

Proof. The first equality follows from Corollary 5.2 and Proposition 5.5.

Also the inclusions $\mathcal{DW}\subseteq
n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}$ and $\mathcal{DW}\subseteq
n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{3}$ hold by Corollary 5.2 and
Proposition 5.5. On the other hand, if $L\in
n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}$, then $L\neq\emptyset$, $L\in
Rec(X)$, and $X^{*}LX^{*}=L$ by Proposition 4.5 (a,b). Thus
$L\in\mathcal{DW}(X)$ by Proposition 5.3. Hence,
$\mathcal{DW}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}$. The equality
$\mathcal{DW}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{3}$ has a similar
proof. $\Box$

###### Proposition 5.7

$\mathcal{D\\!D}_{1}\parallel\mathcal{D\\!D}_{3}$.

Proof. There are two noninclusions to be shown.

If $\mathcal{D\\!D}_{1}\subseteq\mathcal{D\\!D}_{3}$, then naturally also
$n\mathcal{D\\!D}_{1}\subseteq\mathcal{D\\!D}_{3}$. By Proposition 5.6, this
would imply that
$n\mathcal{D\\!D}_{1}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{3}=\mathcal{DW}$,
which contradicts Proposition 5.5 (a). Thus
$\mathcal{D\\!D}_{1}\nsubseteq\mathcal{D\\!D}_{3}$.

To prove $\mathcal{D\\!D}_{3}\nsubseteq\mathcal{D\\!D}_{1}$, let
$\mathcal{F}=(A,X,f)$ be the FFA, where $A=\\{p,q\\}$, $X=\\{x,y\\}$ and $f$
is defined by

$f(p,x,q)=f(q,x,p)=f(q,x,q)=f(p,y,p)=1.$

Then $x,xxy\in D\\!D_{3}({\mathcal{F}})$ as ${\mathcal{F}}_{p,x}=\\{q/1\\}$,
${\mathcal{F}}_{q,x}=\\{p/1,q/1\\}$, and
${\mathcal{F}}_{p,xxy}=\\{p/1\\}={\mathcal{F}}_{q,xxy}$. Assume that there
exists an FFA $\mathcal{G}=(B,X,g)$ for which
$D\\!D_{1}({\mathcal{G}})=D\\!D_{3}({\mathcal{F}})$. Then there would exist
$c,d\in B$ and $r,s\in(0,1]$ such that for every $a\in B$,
${\mathcal{G}}_{a,x}=\\{c/r\\}$ and ${\mathcal{G}}_{a,xxy}=\\{d/s\\}$. Thus,
${\mathcal{G}}(a,x)=\\{c\\}$ for every $a\in B$, and
${\mathcal{G}}(c,x)=\\{c\\}$ in particular. Since
${\mathcal{G}}(a,xxy)=\\{d\\}$ for every $a\in B$, this must means also that
${\mathcal{G}}(c,y)=\\{d\\}$. Moreover, for every $a\in B$, $g(a,x,c)=c$ and
$g(a,x,b)=0$ if $b\neq c$ ($b\in B$). Thus we may conclude that for every
$a\in B$,

$\displaystyle g^{*}(a,xy,d)$ $\displaystyle=\max\\{g(a,x,b)\land g(b,y,d)\mid
b\in B\\}\vspace{-3pt}$ $\displaystyle=g(a,x,c)\land g(c,y,d)=g(a,x,c)\land
g(c,x,c)\land g(c,y,d)$ $\displaystyle=g^{*}(a,xxy,d)=s>0.$

On the other hand, for any $d^{\prime}\neq d$,

$\displaystyle g^{*}(a,xy,d^{\prime})$ $\displaystyle=\max\\{g(a,x,b)\land
g(b,y,d^{\prime})\mid b\in B\\}\vspace{-3pt}$ $\displaystyle=g(a,x,c)\land
g(c,y,d^{\prime})=g(a,x,c)\land g(c,x,c)\land g(c,y,d^{\prime})\vspace{-3pt}$
$\displaystyle\leq g^{*}(a,xxy,d^{\prime})=0.$

Thus ${\mathcal{G}}_{a,xy}=\\{d/s\\}$, for every $a\in B$. This would mean
that $xy\in D\\!D_{1}({\mathcal{G}})$ although $xy\notin
D\\!D_{3}({\mathcal{F}})$ (as ${\mathcal{F}}_{p,xy}=\emptyset$). $\Box$

###### Proposition 5.8

$\mathcal{D\\!D}_{1}\nsubseteq\mathcal{D\\!D}_{2}$ and
$\mathcal{D\\!D}_{3}\nsubseteq\mathcal{D\\!D}_{2}$.

Proof. The noninclusion $\mathcal{D\\!D}_{1}\nsubseteq\mathcal{D\\!D}_{2}$
must hold because $\mathcal{D\\!D}_{1}\subseteq\mathcal{D\\!D}_{2}$ would
imply that
$n\mathcal{D\\!D}_{1}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{1}\subseteq
n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}=\mathcal{DW}\subset
n\mathcal{D\\!D}_{1}$, a contradiction.

To prove $\mathcal{D\\!D}_{3}\nsubseteq\mathcal{D\\!D}_{2}$, consider the FFA
${\mathcal{F}}=(\\{a,b\\},\\{x,y\\},f)$, where $f$ is defined by
$f(a,x,a)=f(a,x,b)=f(a,y,a)=f(b,x,b)=1$. Assume then that
$DD_{3}({\mathcal{F}})=DD_{2}({\mathcal{G}})$ for some FFA ${\mathcal{G}}$.
Now $x\in DD_{3}({\mathcal{F}})$ because ${\mathcal{F}}_{a,x}=\\{a/1,b/1\\}$
and ${\mathcal{F}}_{b,x}=\\{b/1\\}$. However, $x\in DD_{2}({\mathcal{G}})$
would imply $xy\in DD_{2}({\mathcal{G}})$ although $xy\notin
DD_{3}({\mathcal{F}})$. $\Box$

###### Proposition 5.9

$n\mathcal{D\\!D}_{1}\parallel\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}$.

Proof. If
$n\mathcal{D\\!D}_{1}\subseteq\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}$,
then $n\mathcal{D\\!D}_{1}\subseteq\mathcal{D\\!D}_{2}$. By Proposition 5.6,
this would imply that
$\mathcal{DW}=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}=n\mathcal{D\\!D}_{1}$,
which contradicts Proposition 5.5 (a). On the other hand, if
$\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}\subseteq
n\mathcal{D\\!D}_{1}$, then

$\displaystyle\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}$
$\displaystyle=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}\vspace{-3pt}$
$\displaystyle=n\mathcal{D\\!D}_{1}\cap\mathcal{D\\!D}_{2}\cap\mathcal{D\\!D}_{3}\vspace{-3pt}$
$\displaystyle=\mathcal{DW}\cap\mathcal{D\\!D}_{3}\vspace{-3pt}=\mathcal{DW},$

by Propositions 5.5 (a) and 5.6. This would contradict Proposition 5.4. $\Box$

##  6 Classes of DD$i$–directable FFAs

In this section we shall consider the classes of FFAs and normal FFAs with the
various DD$i$–directability properties. For each $i=1,2,3$, let

(1) $\mathbf{DD}(i)$ denote the class of all DD$i$–directable FFAs, and

(2) $\mathbf{nDD}(i)$ denote the class of all DD$i$–directable normal FFAs.
Furthermore, let $\mathbf{Dir}$ be the class of all directable DFAs; recall
that in Section 5 we interpreted with each DFA ${\mathcal{A}}$ a crisp FFA
${\mathcal{A}}^{{\mathbf{f}}{\mathbf{z}}}$.

The following proposition justifies the Hasse diagram of Figure 1 of the
$\cap$-semilattice of the classes $\mathbf{DD}(i)$, $\mathbf{nDD}(i)$,
$\mathbf{Dir}$ and their intersections.

###### Proposition 6.1

  * (a)

$\mathbf{nDD}(i)\subset\mathbf{DD}(i)$ for $i=1,2,3$.

  * (b)

$\mathbf{DD}(1)\subset\mathbf{DD}(2)\cap\mathbf{DD}(3)$.

  * (c)

$\mathbf{DD}(2)\parallel\mathbf{DD}(3)$.

  * (d)

$\mathbf{DD}(2)\cap\mathbf{DD}(3)\subset\mathbf{DD}(2)$ and
$\mathbf{DD}(2)\cap\mathbf{DD}(3)\subset\mathbf{DD}(3)$.

  * (e)

$\mathbf{nDD}(1)\subset\mathbf{nDD}(2)$.

  * (f)

$\mathbf{nDD}(2)\subset\mathbf{nDD}(3)$.

  * (g)

$\mathbf{DD}(1)\parallel\mathbf{nDD}(2)$.

  * (h)

$\mathbf{DD}(2)\cap\mathbf{DD}(3)\parallel\mathbf{nDD}(3)$.

  * (i)

$\mathbf{nDD}(2)\subset\mathbf{DD}(2)\cap\mathbf{DD}(3)$.

  * (j)

$\mathbf{DD}(1)\cap\mathbf{nDD}(2)=\mathbf{nDD}(1)$.

  * (k)

$(\mathbf{DD}(2)\cap\mathbf{DD}(3))\cap\mathbf{nDD}(3)=\mathbf{nDD}(2)$.

  * (l)

$\mathbf{Dir}\subset\mathbf{nDD}(1)$.

$\psmatrix[colsep=10mm,rowsep=9mm]&\rnode{DD2}{{\mathbf{DD}(2)}}\rnode{DD3}{{\mathbf{DD}(3)}}\\\
\rnode{DD2DD3}{{\mathbf{DD}(2)}\cap{\mathbf{DD}(3)}}\rnode{nDD3}{{\mathbf{nDD}(3)}}\\\
\rnode{DD1}{{\mathbf{DD}(1)}}\rnode{nDD2}{{\mathbf{nDD}(2)}}\\\
\rnode{nDD1}{{\mathbf{nDD}(1)}}\\\ \rnode{Dir}{\mathbf{Dir}}$

Figure 1:  Classes of DD-directable FFAs

Proof. (a) $\mathbf{nDD}(i)\subset\mathbf{DD}(i)$ for $i=1,2,3$:
The inclusions are obvious. It is easy to show that they are proper by finding
for each $i=1,2,3$ an FFA that is DD$i$–directable but not normal.

(b) $\mathbf{DD}(1)\subset\mathbf{DD}(2)\cap\mathbf{DD}(3)$:
The inclusion follows from Proposition 4.1 (d). That it is proper, can be seen
by considering the FFA $\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$,
$X=\\{x\\}$, and $f(a,x,a)=f(a,x,b)=f(b,x,a)=f(b,x,b)=1$. For any $w=x^{n}$,
where $n\geq 1$, ${\mathcal{F}}_{a,w}=\\{a/1,b/1\\}={\mathcal{F}}_{b,w}$. Thus
$D\\!D_{2}({\mathcal{F}})=D\\!D_{3}({\mathcal{F}})=\\{x^{n}\mid n\geq 1\\}$,
while $D\\!D_{1}({\mathcal{F}})=\emptyset$.

(c) $\mathbf{DD}(2)\parallel\mathbf{DD}(3)$:
Consider the FFA $\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$, $X=\\{x,y\\}$,
$f(a,x,a)=0.2$, $f(a,x,b)=f(a,y,a)=f(b,x,b)=f(b,y,b)=1$. If $w=y^{n}$ with
$n\geq 1$, then ${\mathcal{F}}_{a,w}=\\{a/1\\}$ and
${\mathcal{F}}_{b,w}=\\{b/1\\}$, which means that $w$ is not DD2–directing. If
the letter $x$ appears in $w\in X^{*}$ at least once, then
${\mathcal{F}}_{a,w}=\\{a/0.2,b/1\\}$ and ${\mathcal{F}}_{b,w}=\\{b/1\\}$, and
thus $w\in D\\!D_{3}({\mathcal{F}})\setminus D\\!D_{2}({\mathcal{F}})$. This
means that ${\mathcal{F}}\in\mathbf{DD}(3)\setminus\mathbf{DD}(2)$.

Next, let ${\mathcal{G}}=(\\{a,b\\},\\{x\\},g)$ be the FFA, where the only
nonzero transition is $g(a,x,b)=1$. Obviously,
${\mathcal{G}}_{a,x}=\\{b/1\\}$, ${\mathcal{G}}_{b,x}=\emptyset$, and
${\mathcal{G}}_{a,w}={\mathcal{G}}_{b,w}=\emptyset$ for any $w=x^{n}$ with
$n\geq 2$. This shows that
${\mathcal{G}}\in\mathbf{DD}(2)\setminus\mathbf{DD}(3)$.

(d) $\mathbf{DD}(2)\cap\mathbf{DD}(3)\subset\mathbf{DD}(2)$ and
$\mathbf{DD}(2)\cap\mathbf{DD}(3)\subset\mathbf{DD}(3)$:
The properness of these inclusions follows from (c).

(e) $\mathbf{nDD}(1)\subset\mathbf{nDD}(2)$:
By (b), any DD1–directable FFA is also DD2–directable, and naturally this
applies to normal FFAs, too. The properness of the inclusion is shown by the
FFA ${\mathcal{F}}$ used in the proof of (b) as it is also normal.

(f) $\mathbf{nDD}(2)\subset\mathbf{nDD}(3)$:
Let $\mathcal{F}=(A,X,f)$ be a DD2–directable normal FFA, and consider any
$w\in D\\!D_{2}({\mathcal{F}})$ and $b\in A$. Since ${\mathcal{F}}$ is normal,
$f^{*}(b,w,c)=1$ for some $c\in A$. As $w$ is DD2–directing, this implies that
$f^{*}(a,w,c)=1$ for every $a\in A$, and thus $w$ is also DD3–directing. To
show that the inclusion $\mathbf{nDD}(2)\subseteq\mathbf{nDD}(3)$ is proper,
consider the FFA ${\mathcal{F}}\in\mathbf{DD}(3)\setminus\mathbf{DD}(2)$ used
in the proof of (c). Since ${\mathcal{F}}$ is normal, also
${\mathcal{F}}\in\mathbf{nDD}(3)\setminus\mathbf{nDD}(2)$ holds.

(g) $\mathbf{DD}(1)\parallel\mathbf{nDD}(2)$:
Consider the FFA $\mathcal{F}=(A,X,f)$, where $A=\\{a,b\\}$, $X=\\{x,y\\}$,
and $f$ is given by $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$. It is in $\mathbf{DD}(1)$
because ${\mathcal{F}}_{a,x}={\mathcal{F}}_{b,x}=\\{b/1\\}$, but it is not in
$\mathbf{nDD}(2)$ as it is not normal. On the other hand,
$\mathbf{nDD}(2)\subseteq\mathbf{DD}(1)$ cannot hold either because
$\mathbf{nDD}(2)\setminus\mathbf{nDD}(1)\neq\emptyset$ by statement (e).

(h) $\mathbf{DD}(2)\cap\mathbf{DD}(3)\parallel\mathbf{nDD}(3)$:
The FFA ${\mathcal{F}}=(\\{a,b\\},\\{x\\},f)$ with $f$ defined by
$f(a,x,b)=f(b,x,b)=0.5$ is DD2– and DD3–directable, but it is not normal. The
FFA ${\mathcal{G}}=(\\{a,b,c\\},\\{x\\},g)$, in which $g$ is given by
$g(a,x,b)=0.5$ and $g(a,x,a)=g(b,x,c)=g(c,x,c)=1$, is normal and
DD3–directable. For example, $xx\in D\\!D_{3}({\mathcal{G}})$. On the other
hand, there are no DD2–directing words as
${\mathcal{G}}_{a,x}=\\{a/1,b/0.5\\}$,
${\mathcal{G}}_{b,x}={\mathcal{G}}_{c,x}=\\{c/1\\}$, and
${\mathcal{G}}_{a,w}=\\{a/1,c/0.5\\}$,
${\mathcal{G}}_{b,w}={\mathcal{G}}_{c,w}=\\{c/1\\}$ for any $w=x^{n}$ with
$n\geq 2$.

(i) $\mathbf{nDD}(2)\subset\mathbf{DD}(2)\cap\mathbf{DD}(3)$:
Of course, $\mathbf{nDD}(2)\subseteq\mathbf{DD}(2)$, and by using statements
(f) and (a), we get
$\mathbf{nDD}(2)\subseteq\mathbf{nDD}(3)\subseteq\mathbf{DD}(3)$. Thus
$\mathbf{nDD}(2)\subseteq\mathbf{DD}(2)\cap\mathbf{DD}(3)$. The FFA
${\mathcal{F}}$ used in the proof of (h) is DD2– and DD3–directable, but it is
not normal. Hence, the inclusion is proper.

(j) $\mathbf{DD}(1)\cap\mathbf{nDD}(2)=\mathbf{nDD}(1)$:
The inclusion $\mathbf{nDD}(1)\subseteq\mathbf{DD}(1)\cap\mathbf{nDD}(2)$
holds because $\mathbf{nDD}(1)\subseteq\mathbf{DD}(1)$ by (a), and
$\mathbf{nDD}(1)\subseteq\mathbf{nDD}(2)$ by (e). On the other hand, if
${\mathcal{F}}\in\mathbf{DD}(1)\cap\mathbf{nDD}(2)$, then ${\mathcal{F}}$ is
both DD1–directable and normal, i.e., ${\mathcal{F}}\in\mathbf{nDD}(1)$.

(k) $(\mathbf{DD}(2)\cap\mathbf{DD}(3))\cap\mathbf{nDD}(3)=\mathbf{nDD}(2)$:
Obviously, (k) is equivalent to the equality
$\mathbf{DD}(2)\cap\mathbf{nDD}(3)=\mathbf{nDD}(2)$ which has a similar proof
as (j).

(l) $\mathbf{Dir}\subset\mathbf{nDD}(1)$:
Any DFA is clearly normal when viewed as an FFA, and by Lemma 5.1 is
DD1–directable. On the other hand, the FFA $\mathcal{F}=(A,X,f)$, where
$A=\\{a,b,c\\}$, $X=\\{x\\}$, and $f$ is given by
$f(a,x,b)=f(a,x,c)=f(b,x,c)=f(c,x,c)=1$, is DD1–directable and normal, but not
a DFA. $\Box$

Let us now consider the subautomata, epimorphic images and finite direct
products of DD1–, DD2– and DD3–directable FFAs. In what follows,
$\mathcal{F}=(A,X,f)$ and $\mathcal{G}=(B,X,g)$ are any two FFAs.

We call ${\mathcal{G}}$ a _subautomaton_ of ${\mathcal{F}}$ if (1) $B\subseteq
A$, (2) ${\mathcal{F}}(b,x)\subseteq B$ for all $b\in B$ and $x\in X$, and (3)
$g(b,x,b^{\prime})=f(b,x,b^{\prime})$ for all $b,b^{\prime}\in B$ and $x\in
X$.

###### Lemma 6.2

Let ${\mathcal{G}}$ be a subautomaton of ${\mathcal{F}}$. For any $b\in B$ and
$w\in X^{*}$,

  * (a)

${\mathcal{F}}(b,w)\subseteq B$,

  * (b)

${\mathcal{G}}(b,w)={\mathcal{F}}(b,w)$, and

  * (c)

${\mathcal{G}}_{b,w}={\mathcal{F}}_{b,w}|_{B}$ (= the restriction of
${\mathcal{F}}_{b,w}$ to $B$).

Proof. All three statements have easy proofs by induction on $\mathrm{lg}(w)$.
$\Box$

###### Proposition 6.3

Let ${\mathcal{G}}$ be a subautomaton of an FFA ${\mathcal{F}}$. For each
$i=1,2,3$, $D\\!D_{i}({\mathcal{F}})\subseteq D\\!D_{i}({\mathcal{G}})$, and
thus any subautomaton of a DD$i$–directable FFA is also DD$i$–directable.
Furthermore, if ${\mathcal{F}}$ is normal, then so is ${\mathcal{G}}$.

Proof. If $w\in D\\!D_{1}({\mathcal{F}})$, then there exist $c\in A$ and
$r\in(0,1]$ such that ${\mathcal{F}}_{a,w}=\\{c/r\\}$ for every $a\in A$. In
particular, for any $b\in B$, $c\in{\mathcal{F}}(b,w)\subseteq B$, and hence
${\mathcal{G}}_{b,w}={\mathcal{F}}_{b,w}|_{B}=\\{c/r\\}$. This means that
$w\in D\\!D_{1}({\mathcal{G}})$.

If $w\in D\\!D_{2}({\mathcal{F}})$, then
${\mathcal{G}}_{a,w}={\mathcal{F}}_{a,w}|_{B}={\mathcal{F}}_{b,w}|_{B}={\mathcal{G}}_{b,w}$
for all $a,b\in B$, i.e., $w\in D\\!D_{2}({\mathcal{G}})$.

Let $w\in D\\!D_{3}({\mathcal{F}})$, and let $c\in A$ be such that for every
$a\in A$, ${\mathcal{F}}_{a,w}(c)>0$ and ${\mathcal{F}}_{a,w}$ is maximal
among all the values of ${\mathcal{F}}_{a,w}$. Since this holds also for every
$a\in B$, we have $c\in B$, and therefore $w\in D\\!D_{3}({\mathcal{G}})$.

Assume now that ${\mathcal{F}}$ is normal, and consider any $b\in B$ and $x\in
X$. Since ${\mathcal{F}}$ is normal, there is a state $c\in A$ such that
$f(b,x,c)=1$. By Lemma 6.2, $c\in B$ and $g(b,x,c)=f(b,x,c)=1$, which shows
that ${\mathcal{G}}$ is normal. $\Box$

A mapping $\varphi:A\rightarrow B$ defines a _homomorphism_
$\varphi:{\mathcal{F}}\rightarrow{\mathcal{G}}$ of FFAs (cf. [19, 20, 21], for
example) if

$g(a\varphi,x,b)=\max\\{f(a,x,a^{\prime})\mid a^{\prime}\in
b\varphi^{-1}\\},\vspace{-3pt}$

for all $a\in A$, $b\in B$ and $x\in X$. A surjective homomorphism is called
an _epimorphism_.

###### Lemma 6.4

If $\varphi:{\mathcal{F}}\rightarrow{\mathcal{G}}$ is an epimorphism of FFAs,
then for all $a\in A$, $b\in B$ and $w\in X^{*}$,

  * (a)

$g^{*}(a\varphi,w,b)=\max\\{f^{*}(a,w,a^{\prime})\mid a^{\prime}\in
b\varphi^{-1}\\}$, and

  * (b)

${\mathcal{F}}(a,w)\varphi={\mathcal{G}}(a\varphi,w)$.

Proof. Statement (a) has a straightforward proof by induction on
$\mathrm{lg}(w)$.

Let us consider (b). Also here we proceed by induction on $\mathrm{lg}(w)$.

If $a^{\prime}\in{\mathcal{F}}(a,w)$, then

$g^{*}(a\varphi,w,a^{\prime}\varphi)=\max\\{f^{*}(a,w,a^{\prime\prime})\mid
a^{\prime\prime}\in A,a^{\prime\prime}\varphi=a^{\prime}\varphi\\}\geq
f(a,w,a^{\prime})>0\vspace{-3pt}$

implies that $a^{\prime}\varphi\in{\mathcal{G}}(a\varphi,w)$, and hence that
${\mathcal{F}}(a,w)\varphi\subseteq{\mathcal{G}}(a\varphi,w)$. Conversely, if
$b\in{\mathcal{G}}(a\varphi,w)$, then

$\max\\{f^{*}(a,w,a^{\prime})\mid a^{\prime}\in
b\varphi^{-1}\\}=g^{*}(a\varphi,w,b)>0\vspace{-3pt}$

means that $f^{*}(a,w,a^{\prime})>0$, i.e., $a^{\prime}\in{\mathcal{F}}(a,w)$,
for some $a^{\prime}\in b\varphi^{-1}$, and thus
$b\in{\mathcal{F}}(a,w)\varphi$. $\Box$

###### Proposition 6.5

If $\varphi:{\mathcal{F}}\rightarrow{\mathcal{G}}$ is an epimorphism of FFAs,
then $D\\!D_{i}({\mathcal{F}})\subseteq D\\!D_{i}({\mathcal{G}})$ for
$i=1,2,3$, and thus all epimorphic images of a DD$i$–directable FFA are
DD$i$–directable. Moreover, if ${\mathcal{F}}$ is normal, then so is
${\mathcal{G}}$.

Proof. Let us prove $D\\!D_{i}({\mathcal{F}})\subseteq
D\\!D_{i}({\mathcal{G}})$ for each value of $i$.

If $w\in D\\!D_{1}({\mathcal{F}})$, then there exist a $c\in A$ and an
$r\in(0,1]$ satisfying ${\mathcal{F}}_{a,w}=\\{c/r\\}$ for every $a\in A$.
Consider any $b\in B$. Since $\varphi$ is surjective, $b=a\varphi$ for some
$a\in A$. For any $d\in B$,

$g^{*}(b,w,d)=\max\\{f^{*}(a,w,a^{\prime})\mid a^{\prime}\in
d\varphi^{-1}\\}=\left\\{\begin{array}[]{cl}r,&\ \mbox{if }d=c\varphi\\\ 0,&\
\mbox{if }d\neq c\varphi.\vspace{-3pt}\end{array}\right.$

This means that ${\mathcal{G}}_{b,w}=\\{c\varphi/r\\}$ for every $b\in B$, and
thus $w\in D\\!D_{1}({\mathcal{G}})$.

If $w\in D\\!D_{2}({\mathcal{F}})$, then $f^{*}(a_{1},w,a)=f^{*}(a_{2},w,a)$
for all $a_{1},a_{2},a\in A$. Consider any states $b_{1},b_{2}\in B$ of
${\mathcal{G}}$, and let $a_{1},a_{2}\in A$ be states of ${\mathcal{F}}$ for
which $b_{1}=a_{1}\varphi$ and $b_{2}=a_{2}\varphi$. For any $b\in B$,

$\displaystyle g^{*}(b_{1},w,b)$ $\displaystyle=\max\\{f^{*}(a_{1},w,a)\mid
a\in b\varphi^{-1}\\}\vspace{-3pt}$ $\displaystyle=\max\\{f^{*}(a_{2},w,a)\mid
a\in b\varphi^{-1}\\}=g^{*}(b_{2},w,b),\vspace{-3pt}$

which shows that $w\in D\\!D_{2}({\mathcal{G}})$.

Let $w\in D\\!D_{3}({\mathcal{F}})$. Then there is a $c\in A$ such that, for
every $a\in A$, $f^{*}(a,w,c)>0$ and $f^{*}(a,w,d)\leq f^{*}(a,w,c)$ for every
$d\in A$. Consider any $b,b^{\prime}\in B$, and let $a,a^{\prime}\in A$ be
states for which $b=a\varphi$ and $b^{\prime}=a^{\prime}\varphi$. Then

$g^{*}(b,w,c\varphi)=\max\\{f^{*}(a,w,a^{\prime\prime})\mid
a^{\prime\prime}\varphi=c\varphi\\}\geq f^{*}(a,w,c)>0,\vspace{-3pt}$

and

$g^{*}(b,w,b^{\prime})=\max\\{f^{*}(a,w,a^{\prime\prime})\mid
a^{\prime\prime}\in b^{\prime}\varphi^{-1}\\}\leq f^{*}(a,w,c)\leq
g^{*}(b,w,c\varphi),$

which means that $w\in D\\!D_{3}({\mathcal{G}})$.

Assume now that ${\mathcal{F}}$ is normal, and consider any $b\in B$ and $x\in
X$. If $a\in A$ and $c\in A$ are states for which $a\varphi=b$ and
$f(a,x,c)=1$, then

$g(b,x,c\varphi)=g(a\varphi,x,c\varphi)=\max\\{f(a,x,d)\mid
d\varphi=c\varphi\\}\geq f(a,x,c)=1,$

i.e., $g(b,x,c\varphi)=1$. $\Box$

The _direct product_ (cf. [19, 20], for example) of two FFAs ${\mathcal{F}}$
and ${\mathcal{G}}$ is the FFA ${\mathcal{F}}\times{\mathcal{G}}=(A\times
B,X,h)$, where $h$ is defined by

$h((a,b),x,(a^{\prime},b^{\prime}))=f(a,x,a^{\prime})\land
g(b,x,b^{\prime})\quad(a,a^{\prime}\in A,b,b^{\prime}\in B,x\in
X).\vspace{-3pt}$

The following example shows that DD$i$–directability ($i=1,2,3$) is not
preserved under this product.

###### Example 6.6

Let ${\mathcal{F}}=(\\{a,b\\},\\{x,y\\},f)$ and
${\mathcal{G}}=(\\{1,2\\},\\{x,y\\},g)$ be FFAs, where $f$ and $g$ are given
by $f(a,x,b)=f(b,x,b)=f(b,y,b)=1$, and $g(1,y,2)=g(2,y,2)=g(2,x,2)=1$. These
FFAs belong to all three classes $\mathbf{DD}(1)$, $\mathbf{DD}(2)$ and
$\mathbf{DD}(3)$ because $x\in D\\!D_{1}({\mathcal{F}})\cap
D\\!D_{2}({\mathcal{F}})\cap D\\!D_{3}({\mathcal{F}})$ and $y\in
D\\!D_{1}({\mathcal{G}})\cap D\\!D_{2}({\mathcal{G}})\cap
D\\!D_{3}({\mathcal{G}})$.

As
$({\mathcal{F}}\times{\mathcal{G}})((a,1),x)=({\mathcal{F}}\times{\mathcal{G}})((a,1),y)=\emptyset$
while
$({\mathcal{F}}\times{\mathcal{G}})((b,2),x)=({\mathcal{F}}\times{\mathcal{G}})((b,2),y)=\\{(b,2)\\}\neq\emptyset$,
it is clear that ${\mathcal{F}}\times{\mathcal{G}}$ has no DD1–, DD2– or
DD3–directing words, and thus
${\mathcal{F}}\times{\mathcal{G}}\notin\mathbf{DD}(1)\cup\mathbf{DD}(2)\cup\mathbf{DD}(3)$.

## References

  * [1] M.A. Arbib, _Theories of Abstract Automata_ , Prentice-Hall, Englewood Cliffs, N.J., 1969.
  * [2] S. Bogdanović, B. Imreh, M. Ćirić and T. Petković, Directable automata and their generalizations: a survey, _Novi Sad Journal of Mathematics_ 29, No. 2 (1999), 19-69.
  * [3] H.V. Burkhard, Zum Längenproblem homogener Experimente an determinierten und nicht-determinierten Automaten, _Elektronische Informationsverarbeiterung und Kybernetik, EIK_ 12 (1976), 301-306.
  * [4] J. $\check{\rm C}$ern$\acute{\rm y}$, Poznámka k homogénnym experimentom s kone$\check{\rm c}$nými automatmi. Matematicko-fysikalny $\check{\rm C}$asopis SAV 14 (1964), 208-215.
  * [5] H. Don and H. Zantema, Synchronizing non-deterministic finite automata, _Journal of Automata, Languages and Combinatorics_ 23, No. 4 (2018), 307-328.
  * [6] Zs. Gazdag, Sz. Iván and J. Nagy-Görgy: Improved upper bounds on synchronizing nondeterministic automata, _Information Processing Letters_ 109 (2009), 986-990.
  * [7] P. Goralčik, Z. Hedrlín, V. Koubek and J. Ryšlinková, A game of composing binary relations, _R.A.I.R.O. Informatique théorique/Theoretical Informatics_ 16(4) (1982), 365-369.
  * [8] J.E. Hopcroft, R. Motwani and J.D. Ullman, _Automata, Languages, and Computation_ (3. ed.), Pearson Boston 2007.
  * [9] B. Imreh and M. Ito, On some special classes of regular languages, in: J. Karhumäki, H. Maurer, G. Paun, G. Rozenberg (eds.), _Jewels are Forever_ , Springer, Berlin 1999, pp. 25-34.
  * [10] B. Imreh, M. Ito and M. Steinby, On commutative directable nondeterministic automata, in: C. Martin-Vide and V. Mitrana (eds.), _Grammars and Automata for String Processing. From Mathematics and Computer Science to Biology, and Back_ , Taylor and Francis, London 2003, pp. 141-150.
  * [11] B. Imreh and M. Steinby, Some Remarks on Directable Automata, _Acta Cybernetica_ 12 (1995), 23-35.
  * [12] B. Imreh and M. Steinby, Directable nondeterministic automata, _Acta Cybernetica_ 14 (1999), 105-115.
  * [13] M. Ito, _Algebraic Theory of Automata and Languages_ , World Scientific Publishing Co., Singapore 2004.
  * [14] M. Ito and K. Shikishima-Tsuji, Shortest directing words of nondeterministic directable automata, _Discrete Mathematics_ 308 (2008), 4900-4905.
  * [15] Sz. Iván, Synchronizing weighted automata, in: Z. Ésik and Z. Fülöp (eds.), _Automata and Formal Languages_ (AFL 2014), EPTCS 151 (2014), 301-313.
  * [16] V. Karthikeyan and M. Rajasekar, Directable Fuzzy Automata, _International Journal of Computer Applications_ (0975-8887) 125, No. 8 (2015).
  * [17] D.J. Kfoury, Synchronizing sequences of probabilistic automata, _Studies in Applied Mathematics_ 49 (1970), 101-103.
  * [18] D.C. Kozen, _Automata and Computability_ , Springer-Verlag, New York 1997.
  * [19] D.S. Malik, J.N. Mordeson and M.K. Sen, Products of fuzzy finite state machines, _Fuzzy Sets and Systems_ 92 (1997), 95-102.
  * [20] J. Mordeson and D. Malik, _Fuzzy Automata and Languages: Theory and Applications_ , Chapman & Hall (CRC), London 2002.
  * [21] T. Petković, Congruences and homomorphisms of fuzzy automata, _Fuzzy Sets and Systems_ 157 (2006), 444-458.
  * [22] G. Rahonis, Fuzzy languages, in: M. Droste, W. Kuich, and H. Vogler (eds.), _Handbook of Weighted Automata_ , Springer-Verlag, Berlin 2009. pp. 481-517.
  * [23] J. Sakarovich, _Elements of Automata Theory_ , Cambridge University Press, Cambridge 2009.
  * [24] A. Salomaa, _Theory of Automata_ , Pergamon Press, Oxford, 1969.
  * [25] H. Shabana, $D_{2}$-synchronization in nondeterministic automata, _Ural Mathematical Journal_ 4, No. 2 (2018), 99-110.
  * [26] M.V. Volkov, Synchronizing automata and the C̆erný conjecture, in: C. Martín-Vide, F. Otto and H. Fernau (eds.), _LATA 2008_ , Lecture Notes in Computer Science 5196, Springer-Verlag, Berlin 2008, pp. 11-27.
  * [27] L.A. Zadeh, Fuzzy sets, _Information and Control_ 8 (1965), 338-353.