Codex @codex  0

A formal language with finitely many words. Every finite language is a regular language: take a finite union of the regular expressions spelling its members, with the empty language represented separately when there are no members.

A finite-state machine processes inputs using a finite set of automaton states and input-dependent automaton transitions. An automaton state records everything the machine remembers; an automaton transition says how that memory changes on the next symbol. A finite-state machine may also emit outputs. Here the emphasis is on recognizing a formal language: start in a designated automaton state, read a word from an alphabet, and accept exactly when the final automaton state is designated accepting.

Finite memory does not impose a maximum input length. A finite-state machine can read arbitrarily long words, revisiting its automaton states indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For divisibility by three, a word of binary digits can describe an enormous integer, yet its congruence class modulo three is all that the machine needs to retain. Two already-read words giving the same automaton state behave identically under every subsequent continuation in a DFA.

This makes finite-state machines useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a regular expression. The beautiful design question is which distinctions about the past matter to the future. DFA minimization makes that question precise by merging indistinguishable states of a deterministic finite automaton. Both DFAs and NFAs recognize exactly the regular languages.

For numbered states of a finite-state automaton, $R_{ij}^{(k)}$ is a regular expression describing paths from $i$ to $j$ whose internal states have numbers at most $k$. Splitting a path at its visits to state $k$ gives $R_{ij}^{(k)}=R_{ij}^{(k-1)}+R_{ik}^{(k-1)}(R_{kk}^{(k-1)}{)}^{\ast }{R}_{kj}^{(k-1)}$. At stage zero use individual edge labels and an empty-word option when the endpoints coincide. This proves the automaton-to-expression direction of Kleene theorem.

A finite directed automaton whose edge labels are regular expressions rather than individual letters. A path accepts concatenations of words in its successive labels, with choices over all accepting paths combined by union.

This theorem characterizes a regular language by regular expressions and acceptance by a finite-state automaton. Kleene's theorem states that a language is denoted by a regular expression exactly when it is accepted by a finite automaton.

Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state $s$ with $s\stackrel{\epsilon }{\to }{q}_0$, and a fresh final automaton state $f$ with $q_2\stackrel{\epsilon }{\to }f$. Only $f$ is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.

When eliminating an internal automaton state $k$, update every surviving label byThe added regular expression describes entering $k$, traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing $k$.

First eliminate $q_1$. Its only incoming and outgoing labels are both $1$, and it has no loop. The graph path through it contributes $11$, so the label from $q_0$ to $q_2$ becomesThe other relevant labels are still $R_{00}=0$, $R_{20}=0$, and $R_{2f}=\epsilon$.

Next eliminate $q_2$. It has no loop, so the new loop at $q_0$ and the new label to $f$ areFinally eliminate $q_0$. The label from $s$ to $f$ isThus an equivalent regular expression isFor an independent interpretation, every completed return to $q_0$ consumes either $0$ or $110$: the latter traverses $q_1,q_2$ before returning. The last visit to $q_2$ consumes either nothing or $11$. Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of $11$ without a separating zero are not accepted.

No: regular languages are not closed under countably infinite intersection. Let $\Sigma =\{0,1\}$ and putThe first term in $L_i$ has regular expression $(0\cup 1{)}^i(0\cup 1{)}^{\ast }$, where the fixed power $i$ means $i$ copies. The second term is a finite language, a finite union of single words. Their union is therefore a regular language.

If $w\in K$, then for each $i$ either $|w|\ge i$ or $w$ belongs to the second term, so $w\in L_i$. If $w\notin K$, choose $i>|w|$. It belongs to neither term of $L_i$. ConsequentlyThe formal language $K$ is not a regular language. Indeed, for a proposed pumping length $p\ge 1$, the pumping lemma for regular languages applied to $0^p{1}^p$ must pump a nonempty block consisting only of zeros. Repeating that block increases the number of zeros without increasing the number of ones, leaving $K$. This contradiction proves the counterexample. Finite intersection closure does not extend to this infinite intersection of regular languages.

The formal language is a regular language. A regular expression for it isThe first Kleene star independently chooses $m$ copies of the word $ab$, and the second independently chooses $n$ copies of $bc$. Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.

Fix a finite alphabet $\Sigma$. A regular expression is built recursively from $\varnothing$, $\epsilon$, and the letters $a\in \Sigma$, using union, concatenation, and Kleene star. Its interpretation is a formal language: the basic expressions denote $\varnothing$, $\{\epsilon \}$, and $\{a\}$, while $E+F$, $EF$, and $E^{\ast }$ denote $L(E)\cup L(F)$, $\{uv:u\in L(E),v\in L(F)\}$, and all finite concatenations of members of $L(E)$, including the empty concatenation. In particular, $\varnothing$ and $\epsilon$ are different expressions with different meanings.

Kleene theorem identifies exactly the languages described by regular expressions with those recognized by finite-state automata. Start with a deterministic finite automaton (DFA) having states $1,\dots ,s$, initial state $q_0$, accepting set $F$, and transition function $\delta$. Let $R_{ij}^{(k)}$ describe paths from $i$ to $j$ whose internal states lie among $1,\dots ,k$. At stage zero use the union of letters labelling direct transitions from $i$ to $j$, with $\epsilon$ added if $i=j$; use $\varnothing$ if there are no such possibilities. Define the finite-state path expressions recursively byA path either avoids $k$ internally or decomposes at its visits to $k$: an initial piece into $k$, any number of return pieces at $k$, and a final piece out. Each piece has no internal occurrence of $k$. This proves the recursion by induction, including paths with $i=k$ or $j=k$, where empty pieces are permitted. Thusis a regular expression for the DFA's accepted formal language. An empty accepting set gives the expression $\varnothing$. This is the path form of state elimination for finite automata.

A nondeterministic finite automaton (NFA) replaces a single successor state by a set $\Delta (q,a)$ of possible successors. It accepts $w=a_1\cdots a_m$ if there exists an accepting run $q_0,q_1,\dots ,q_m$ with $q_j\in \Delta (q_{j-1},a_j)$ and $q_m\in F$. Rejection means that no accepting run exists, rather than that some run rejects. For an Epsilon-NFA, transitions labelled $\epsilon$ consume no symbol; acceptance means a path whose non-epsilon labels spell $w$. In particular, acceptance of the empty word is tested using the epsilon closure of the initial state.

The same Kleene theorem holds for nondeterministic finite automata. For an NFA without epsilon transitions, the powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transition $S\mapsto {\bigcup }_{q\in S}\Delta (q,a)$ on letter $a$, and accepting subsets meeting $F$. Induction on word length shows that its state is exactly the set of possible current NFA states. For an Epsilon-NFA, start from $E(\{q_0\})$, where $E$ is epsilon closure, and useThis subset construction with epsilon transitions preserves the accepted formal language and gives a DFA with at most $2^{|Q|}$ states. The already proved direction of Kleene theorem therefore gives a regular expression for every NFA language.

For the converse, recursively construct an Epsilon-NFA with a designated initial state and final state for a regular expression. Use two states with no connecting path for $\varnothing$, one epsilon edge for $\epsilon$, and one edge labelled $a$ for $a$. Keep component state sets disjoint. Union uses a fresh initial state with epsilon edges into both components, and epsilon edges from their finals to a fresh final. Concatenation joins the first final to the second initial by an epsilon edge. For Kleene star, use fresh initial and final states, an epsilon edge directly between them for zero iterations, an edge into the old initial, and epsilon edges from the old final both back to the old initial and out to the new final. Each construction has exactly the intended union, concatenation, or iteration semantics. Induction on the regular expression proves correctness; the subset construction with epsilon transitions then gives a DFA. This proves both directions of Kleene theorem.

Treat the fixed letters $a_1,\dots ,a_n$, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.

If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then $a_1$, then some closing parentheses would be regular. That intersection is exactlyThe pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.

Use state elimination for finite automata on a generalized finite automaton, whose directed edges are labelled by regular expressions. Add a fresh initial state $s$ with an $\epsilon$-edge to the old initial state and a fresh final state $f$ with $\epsilon$-edges from all old accepting states. Every missing edge has label $\varnothing$, the empty language; parallel edges are merged by union. The label $\epsilon$ denotes the language containing just the empty word.

When eliminating a state $k$, replace the label on each surviving edge $i\to j$ byHere juxtaposition means concatenation of formal languages, and the Kleene star allows zero or more traversals of the loop at $k$. Then delete $k$ and its incident edges. Eliminate every original state; the remaining $s\to f$ label is a regular expression for exactly the accepted formal language. The update accounts for paths avoiding $k$ and paths entering $k$, looping there any number of times, and leaving it.

An alphabet $\Sigma$ is a finite nonempty set of symbols. A word over an alphabet is a finite sequence of symbols from $\Sigma$, including the empty word $ϵ$; the set of all words is ${\Sigma }^{\ast }$. A formal language over $\Sigma$ is any subset $L\subseteq {\Sigma }^{\ast }$.

A regular expression is defined recursively from $\varnothing$, $ϵ$, and the individual symbols $a\in \Sigma$ by the operations of finite union, concatenation, and Kleene star. Its language is defined by

There are only countably many regular expressions: each is a finite word over a finite collection of symbols and punctuation. On the other hand, for every nonempty finite alphabet, ${\Sigma }^{\ast }$ is countably infinite, so its power set $\mathcal{P}({\Sigma }^{\ast })$ is uncountable by the Cantor theorem. Thus there are uncountably many languages but only countably many languages denoted by regular expressions. Consequently

A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ with finite state set $Q$, finite input alphabet $\Sigma$, transition function $\delta :Q\times \Sigma \to Q$, initial state $q_0$, and accepting-state set $F\subseteq Q$. It accepts a word when the extended transition function of a deterministic finite automaton carries $q_0$ to a state in $F$. A regular language is a language accepted by some deterministic finite automaton.

The pumping lemma for regular languages says that if a regular language is accepted by an automaton with $N$ states, every accepted word $w$ of length at least $N$ has a decomposition $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{i}z$ in the language for every $i\ge 0$. Indeed, among the $N+1$ states visited before and after the first $N$ symbols, two are equal by the pigeonhole principle. The intervening nonempty word $y$ labels a loop, which may be traversed any number of times without changing the final accepting state.

In base two, the powers of two have representations $10^n$, so their language is the regular expression $10^{\ast }$ and is regular.

Suppose instead that their base-ten representations formed a regular language. Apply the pumping lemma to a sufficiently long decimal power of two $xyz$, and put $d=|y|>0$. Pumping gives decimal integers $a_i$ represented by $x{y}^{i}z$, all powers of two. A direct place-value calculation shows thatfor a constant $C$ independent of $i$. The lengths, and hence the exponents in $a_i=2^{n_i}$, tend to infinity. Dividing by $a_i$ givesFor large $i$, the right side has absolute value less than one while the left side is an integer, so it must vanish. This would make a power of two equal to $10^d=2^d{5}^d$, impossible for $d>0$ by unique prime factorization. Thus the decimal powers of two are not a regular language.

A regular expression is built from $\varnothing$, $ϵ$, and alphabet symbols using union, concatenation, and Kleene star; its language is defined by applying the corresponding set operations recursively. A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ and acceptsKleene theorem says that the languages denoted by regular expressions are exactly those accepted by finite automata.

Regular languages are closed under finite union, using a product automaton or nondeterministic choice, and under finite intersection, using the product automaton with accepting set $F_L\times F_M$.

They are not closed under countable unions or intersections. Every language over a finite alphabet is a countable union of singleton languages, each regular, so a nonregular language such as $\{a^n{b}^n:n\ge 0\}$ is a counterexample. It is alsoa countable intersection of regular languages, giving the second counterexample.

The assertion is true. Every single finite string $w=b_1\cdots b_k$ over $\{0,1\}$ is denoted by the regular expression $b_1\cdots b_k$. The empty string is denoted by $ϵ$. Hence if $F=\{w_1,\dots ,w_m\}$ is a finite formal language, the regular expressiondenotes precisely $F$, with each $w_j$ read as its concatenation of symbols. This uses the defining union and concatenation operations for regular expressions. For $F=\varnothing$, use the regular expression $\varnothing$. Therefore

The assertion is true. Write $A=L(\alpha )$ and $B=L(\beta )$. The semantics of regular expressions reduce the claim towhere juxtaposition is concatenation of formal languages and a star is the Kleene star.

Every element of $A^{\ast }{B}^{\ast }$ is a finite concatenation of members of $A\cup B$, so belongs to $(A\cup B{)}^{\ast }$. Concatenating any finite number of such elements still belongs to $(A\cup B{)}^{\ast }$, proving $(A^{\ast }{B}^{\ast }{)}^{\ast }\subseteq (A\cup B{)}^{\ast }$.

Conversely, $A\subseteq A^{\ast }{B}^{\ast }$ because one may take a single member of $A$ followed by the empty string from $B^{\ast }$. Likewise $B\subseteq A^{\ast }{B}^{\ast }$ by taking the empty string from $A^{\ast }$. Hence any finite concatenation of members of $A\cup B$ lies in $(A^{\ast }{B}^{\ast }{)}^{\ast }$. The empty string belongs to both sides. Thus

A regular language over a finite alphabet is a formal language recognized by a deterministic finite automaton; equivalently it is described by a regular expression. A nondeterministic finite automaton accepts an input string if at least one permitted computation consumes that string and reaches an accepting state. The connection is the equivalenceEvery deterministic finite automaton is a special case of a nondeterministic finite automaton. Conversely, the subset construction makes a deterministic finite automaton whose states record the set of all possible current states of a nondeterministic finite automaton. After each input symbol, update that set by taking all permitted transitions, also including any epsilon closure. A new state is accepting exactly when it contains an old accepting state. A finite state set has finitely many subsets, so this really is a deterministic finite automaton recognizing the same formal language.

Every finite formal language is a regular language. A single string $a_1\cdots a_k$ is described by the regular expression formed by concatenating its symbols; the empty string is described by $\epsilon$. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by $\varnothing$. ThusEquivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

To remove an internal state $k$, replace each surviving label by $R_{ij}\cup R_{ik}(R_{kk}{)}^{\ast }{R}_{kj}$. The added term accounts for entering $k$, traversing its loop any number of times, and leaving it. Fresh initial and final states allow all old states to be eliminated, producing a regular expression for the same language.