Access Restriction

Author Reynolds, R. G. ♦ Cutlip, W. F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1969
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let $\textit{s}$ and $\textit{t}$ be states of a finite (deterministic) automaton $\textit{A}.$ $\textit{t}$ can be reached from $\textit{s}$ if there is a tape $\textit{x}$ such that, if $\textit{A}$ is in state $\textit{s}$ and receives $\textit{x},$ $\textit{A}$ goes to state $\textit{t}.We$ consider (1) automata in which the initial state can be reached from any final state, and (2) automata which can be brought to a known state from any unknown state by applying a predetermined tape $\textit{x}.Necessary$ and sufficient conditions for an ultimate definite automaton to have the former property are obtained. Every ultimate definite automaton $\textit{A}$ is shown to have the latter property; and a characterization is obtained for all tapes which bring $\textit{A}$ to a known state. Finally, those ultimate definite automata having the former property are shown to be precisely those which can be brought to the start state from any state by some tape $\textit{x}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1969-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 16
Issue Number 2
Page Count 9
Starting Page 226
Ending Page 234

Open content in new tab

   Open content in new tab
Source: ACM Digital Library