For one of these inputs r, Thompson’s construction can be used to construct a nondeterministic finite automaton where the number of states is upper bounded by the number of operators in r. In Perl, a non-greedy implementation for finding these things is called when a question mark is added after a quantifier. In formal language theory, the union, concatenation, and (*) Kleene star operators over these things produce others of these things in an alphabet. On the command line, grep can be used to search plain text data for these sequences. An asterisk is used to represent zero or more repetitions of a character in these sequences, while the period is the canonical wildcard character in these sequences. For 10 points, find and replace algorithms take what type of sequences as input for pattern matching? ■END■
ANSWER: regular expressions [or regex; prompt on strings]
<KJ, Other Science>
= Average correct buzz position