Necessary and sufficient conditions for a language described by this adjective are given by the Myhill-Nerode theorem.
Systems described by this adjective are equivalent to monadic, second order logic by the Büchi-Elgot-Trakhtenbrot theorem. Necessary and sufficient conditions for a language described by this adjective are given by the Myhill-Nerode theorem. It can be shown that the language "zero the n, one to the n" is a language that does not have this property by invoking the pumping lemma. All finite languages have this property, as well as all languages that can be modeled by (*) nondeterministic and deterministic finite state machines. Wildcards, unions and concatenations are often used to search through text by using a tool with this adjective in its name. For 10 points, name this adjective that describes "expressions" used in searching.
Systems described by this adjective are equivalent to monadic, second order logic by the Büchi-Elgot-Trakhtenbrot theorem.
regular expressions or regular languages