Regulaarset

Regulaarset, in Estonian usage, corresponds to the concept of a regular language in formal language theory. A regulaarset is a set of finite strings over a finite alphabet that can be described or recognised by finite automata. In practice, a language L is regulaarset if it can be accepted by a deterministic finite automaton (DFA) or a nondeterministic finite automaton (NFA), or described by a regular expression, or generated by a regular grammar. Regular languages form the basic class in the Chomsky hierarchy and are closed under union, concatenation, and Kleene star, as well as under intersection and complement.

Key properties include decidability of basic questions: membership testing is decidable by processing the input through the automaton; emptiness, finiteness, and universality are decidable. Every regular language has a minimal DFA, unique up to isomorphism; the equivalence problem for regular languages is decidable by comparing minimized DFAs. The Myhill–Nerode theorem provides a characterization via right-invariant equivalence relations, and the pumping lemma offers a practical method to prove non-regularity.

Examples illustrate the concept. The language (a|b)* over the alphabet {a,b} is regulaarset; the set of strings with no two consecutive a's is regulaarset; the language of strings with an even number of b's is regulaarset. A classical non-regular example is {a^n b^n | n ≥ 0}.

Constructions and representations include regular expressions, NFAs, DFAs, and regular grammars. Thompson’s construction converts a regular expression into an NFA; the subset construction converts an NFA into a DFA; minimization algorithms produce a smallest DFA equivalent to a given automaton.

Historically, the concept arose from Kleene’s work and was later formalized in the theory of regular languages. Regulaarset concepts are foundational in lexical analysis, compiler design, text processing, protocol specification, and formal verification.