% John David Stone
% Department of Mathematics and Computer Science
% Grinnell College
% stone@cs.grinnell.edu

% created June 21, 2002
% last revised June 21, 2002

\documentclass[11pt]{article}

% The \dfa command causes the phrase `deterministic finite automaton' to be
% set.

\newcommand{\dfa}{deterministic finite automaton}

\begin{document}
Theorem 1.19 shows that any non\dfa\ can be converted into an equivalent
\dfa, so if a non\dfa\ recognizes some language, so does some \dfa, and
hence the language is regular.  The other direction states that a language
is regular only if some non\dfa\ recognizes it.  That is, if a language is
regular, some non\dfa\ must be recognizing it.  Obviously, this condition
is true because a regular language has a \dfa\ recognizing it and any
\dfa\ is also a non\dfa.
\end{document}