Nondeterminism and existence of finite‐state supervisors in discrete‐event systems
Toshimitsu Ushio · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1991
Abstract Supervisory control initiated by Ramadge and Wonham is a very useful control technique for discrete‐event systems. A supervisor realized by a finite automaton is called a finite state supervisor. It is clear that a finite state supervisor exists for every regular controllable language. It is very important to show a necessary and sufficient condition for the existence of a finite state supervisor. Moreover, there are few studies for the effect of nondeterminism in a supervisor on control. First, this paper shows that there exists a deterministic finite state supervisor for every control specification for which a nondeterministic finite state supervisor exists. Then a necessary and sufficient condition for the existence of a finite state supervisor is proved. As a result, it is shown that no finite state supervisor exists if a controlled discrete‐event system is modeled by a finite automaton and control specification is given by a nonregular language. Finally, a simple manufacturing system and a nonregular control specification (for which a finite state supervisor exists) are demonstrated.