Directable Nondeterministic Automata
Directable Nondeterministic Automata
复制标题
可定向非确定性自动机
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Steinby
中科院分区：
文献类型：
--
作者：
B. Imreh;M. Steinby
一个自动机是可定向的，如果它有一个引导字，把它从每一个状态带到同一个状态。对于非确定性（n.d.）自动机的可定向性可以用几种有意义的方式来定义。我们考虑三个这样的概念。一个n. d.的输入字w。自动机A是（1）如果A在阅读w之后可能处于的状态集合aw对于所有初始状态a由相同的单个状态c组成，则是D1-定向的;（2）如果集合aw独立于初始状态a，则是D2-定向的;（3）如果某个状态c出现在所有集合aw中，则是D3-定向的。我们考虑给定n. d的D_1、D_2和D_3定向词的集合。自动机，并比较了D1，D2-和D3-有向n.d.机器人彼此我们还估计了n状态n. d的最长可能的最小长度D1，D2和D3定向字的长度。自动机所有的问题都是单独研究的n.d.自动机，每个输入状态对至少有一个下一个状态。
An automaton is directable if it has a directing word which takes it from every state to the same state. For nondeterministic (n.d.) automata directability can be defined in several meaningful ways. We consider three such notions. An input word w of an n.d. automaton A is (1) Dl-directing if the set of states aw in which A may be after reading w consists of the same single state c for all initial states a; (2) D2-directing if the set aw is independent of the initial state a; (3) D3-directing if some state c appears in all of the sets aw. We consider the sets of D1, D2-and D3-directing words of a given n.d. automaton, and compare the classes of D1, D2-and D3-directable n.d. automata with each other. We also estimate the lengths of the longest possible minimum-length D1, D2-and D3-directing words of an n-state n.d. automaton. All questions are studied separately for n.d. automata which have at least one next state for every input-state pair.