Regular language

A formal language is a set of finite strings over an alphabet. It is regular when some finite automaton accepts exactly its members. The restriction concerns the number of machine states, not the length of an input or the number of strings in the language.

A deterministic automaton starts in a designated state and updates its state for each input symbol. After the last symbol, an accepting state means acceptance. For example, recognizing binary strings ending in 01 requires only a few states that record relevant suffix information, rather than a stored copy of the entire input.

References: [1]

Formal regular expressions combine symbols, the empty string and the empty language using union, concatenation and star. These operations mean alternatives, successive joining, and zero or more repetitions. Thus (0|1)*01 describes binary strings ending in 01, including 01 itself because the starred part may contribute nothing. For instance, 1101 belongs to this language, whereas 010 does not. The expression imposes a suffix condition, not a requirement that the total numbers of zeros and ones should be equal.

A nondeterministic finite automaton can offer several possible transitions, including moves that consume no input. It accepts if at least one path consumes the whole string and finishes in an accepting state. A deterministic machine can simulate it by keeping track of the set of possible states. Regular expressions can be converted into such automata, and automata can be converted back into expressions. These are alternative descriptions of the same language class, not different levels of recognition power.

References: [2] [3]

Unlimited repetition does not imply unlimited counting. Consider strings consisting of some number of zeros followed by exactly as many ones. This language is not regular: a finite collection of states cannot preserve a distinct count for every possible length of the first block.

The pumping lemma supplies a proof technique. A sufficiently long accepting computation must revisit a state, creating a segment that can be repeated or removed without changing acceptance. Choosing a suitable long string in the equal-count language makes that modification destroy the required equality. The lemma gives a necessary condition for regularity; simply failing to devise an automaton is not a proof that a language is nonregular.

References: [3]

Practical regex syntax often extends the formal operators. Some additions are convenient abbreviations with no extra expressive power. Backreferences, however, can demand that later input repeat arbitrary text captured earlier, allowing patterns beyond the regular languages. This does not mean every individual pattern containing a backreference is nonregular.

Expressiveness and execution speed are separate questions. Even for a regular language, an engine that repeatedly backtracks through alternatives may behave very differently from a finite-automaton implementation. The name of an API therefore establishes neither a mathematical language class nor a performance guarantee.

References: [4]