Study guides · Intermediate

Formal Languages, Regular Expressions, and Finite Automata

Represent sets of strings with state transitions and distinguish finite-state recognition from unbounded counting.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. A language is a set of strings
  2. Two states are enough for parity
  3. DFA, NFA and regular expressions
  4. Can finite state remember unbounded matching?
  5. Ask Logeia about this articleCheck your understanding

A language is a set of strings

A formal language is a set of strings over an alphabet. Over the alphabet containing zero and one, consider the strings with an even number of ones. A recognizer decides whether a complete input belongs to that set. The empty string also counts as a string and is accepted here because it contains zero ones. Specify the alphabet and acceptance condition before discussing an implementation. Matching a substring inside a longer input is a different interface from recognizing the entire input, even if both interfaces are described casually as regular-expression matching.

Two states are enough for parity

Create state E for an even number of ones and O for an odd number. Reading zero leaves the state unchanged; reading one switches E and O. Start in E and accept only in E. Input 101 follows E, O, O, E and is accepted. The machine does not retain the whole prefix because only parity matters for future decisions. This illustrates what a state summarizes: prefixes with the same relevant future behavior can share one finite memory state, even when the prefixes themselves have arbitrarily different lengths.

DFA, NFA and regular expressions

A deterministic finite automaton has one next state for each state and input symbol. A nondeterministic automaton may offer several paths or transitions that consume no symbol; acceptance requires at least one successful path. Subset construction can turn an NFA into a DFA, but the resulting state space may grow dramatically. Classical regular expressions, DFAs and NFAs describe the same regular languages. Production regex libraries may include backreferences or other extensions beyond that formal model. Identify the supported operators before using an automata theorem to explain a library’s behavior or performance.

Can finite state remember unbounded matching?

Consider strings consisting of n copies of a followed by exactly n copies of b, with no upper bound on n. A finite set of states cannot keep every relevant count distinct. Formal arguments using distinguishable prefixes or regular-language properties establish that no finite automaton recognizes this whole language. A fixed, bounded input length changes the problem: a finite implementation can enumerate the allowed cases. The impossibility claim concerns one finite-state recognizer handling all input lengths, not the impossibility of validating a particular short string or a bounded production format.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 21

Choose a learning path