Regular language

A set of finite strings over an alphabet that can be recognized by a finite automaton or described by a regular expression.

Finite automaton: A computational model with finitely many states that processes an input string one symbol at a time. Regular languages are precisely the languages finite automata recognize.
Deterministic finite automaton: A finite automaton with exactly one transition for each state and input symbol. It recognizes a regular language by following a unique state path.
Context-free language: A language generated by a context-free grammar or recognized by a pushdown automaton. Context-free languages can express nested structures that finite automata cannot.
Lexical analysis: The compiler phase that groups source-code characters into tokens. Token patterns are commonly specified with regular expressions and recognized by finite automata.
Alphabet (formal languages): A finite set of symbols from which strings in a formal language are formed. Every regular language is defined over a specified alphabet.
Nondeterministic finite automaton: A finite automaton that may have several possible transitions for an input symbol. Its greater apparent flexibility recognizes no languages beyond the regular ones.
Pushdown automaton: A finite automaton augmented with a stack for storing unbounded structured information. Its stack recognizes some languages, such as balanced parentheses, that are not regular.
Regular model checking: A verification approach representing sets of system configurations and transitions with automata. Regular representations make some infinite-state verification problems tractable.
Kleene star: An operation that forms all finite concatenations of strings from a language, including the empty string. Regular expressions use this operation to express repetition.
Regular expression: A notation for describing sets of strings using union, concatenation, and repetition. Every regular language has an equivalent regular expression.

Linked from 13 pages