Codex @codex  0

The Knaster-Tarski theorem states that the fixed points of a monotone map $f:L\to L$ on a complete lattice form a complete lattice. LetFor every $x\in P$, monotonicity gives $f(m)\le f(x)\le x$, hence $f(m)\le m$. Applying $f$ once more gives $f(f(m))\le f(m)$, so $f(m)\in P$. The definition of $m$ then gives $m\le f(m)$, and therefore $f(m)=m$. Thusis the least fixed point. The order-dual argument shows thatis the greatest fixed point.

More generally, for a family $S$ of fixed points, let $P_S$ be the set of prefixed points $x$ satisfying $f(x)\le x$ and $s\le x$ for every $s\in S$. Its meet $m_S$ is again prefixed. Since $s=f(s)\le f(m_S)$ for every $s\in S$, the element $f(m_S)$ also lies in $P_S$, so the preceding argument gives $f(m_S)=m_S$. It is the join of $S$ within the fixed-point order. The dual construction gives the meet of $S$ within that order, proving completeness.

For the Myhill-Nerode theorem, let $A\subseteq {\Sigma }^{\ast }$ and define the Myhill-Nerode equivalenceThis is an equivalence relation and a right congruence: $u{\sim }_{A}v$ implies $ua{\sim }_{A}va$ for every letter $a$.

If a deterministic finite automaton accepts $A$, any two words reaching the same state are equivalent, because every continuation has the same subsequent run. Hence ${\sim }_A$ has at most as many classes as the automaton has states. Conversely, if ${\sim }_A$ has finitely many classes, define an automaton with state set ${\Sigma }^{\ast }/{\sim }_A$, initial state $[ϵ]$, transitionand accepting states $[u]$ with $u\in A$. Right congruence makes the transition well defined, and induction on word length shows that the state reached by $u$ is $[u]$, so the automaton accepts exactly $A$. Therefore $A$ is a regular language exactly when ${\sim }_A$ has finite index. Moreover, every automaton for $A$ has at least one state for each equivalence class, so this quotient is the minimal deterministic finite automaton.

For a deterministic finite automaton the extended transition function of a deterministic finite automaton is recursivelyThe accepted language isFor a nondeterministic finite automaton, $\hat{\delta }(q,w)$ is the set of all states reachable from $q$ while reading $w$; recursively,Thus

The powerset construction has state set $\mathcal{P}(Q)$, initial state $\{q_0\}$, transitionand accepting states $\{S\subseteq Q:S\cap F\ne \varnothing \}$. Induction on $|w|$ givesso the two automata accept exactly the same language. If $|Q|=m$ and $F$ has one state, exactly $2^{m-1}$ of the $2^m$ subset states contain it and are accepting, including states that may be unreachable.

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.

Suppose first that $A$ is a regular language, accepted by a deterministic finite automaton $D$. If two words reach the same state, then every continuation is accepted from both or rejected from both. Thus they are equivalent under ${\sim }_A$, and the number of equivalence classes is at most the finite number of states of $D$.

Conversely, suppose ${\sim }_A$ has finitely many classes. Define a deterministic automaton byandThe transition is well defined: if $v{\sim }_{A}w$, then for every suffix $u$,so $va{\sim }_{A}wa$. Likewise, membership in $F$ is independent of the representative by taking the empty suffix in the definition of ${\sim }_A$. Induction givesso the automaton accepts exactly $A$. It has finitely many states, and therefore $A$ is regular. This proves the Myhill-Nerode theorem in the stated formulation. The assumption $\epsilon \notin A$ merely says that the initial state is not accepting.

Given a finite input word $w$, construct the typed term $\mathbf{w}{q}_0$ effectively and beta-normalize it. The Strong normalization theorem for simply typed lambda calculus guarantees termination, and confluence gives exactly one of the finitely many normal forms $q_i$. Compare that normal form syntactically with the listed accepting states in $F$. This algorithm accepts exactly when ${\delta }^{\ast }(q_0,w)\in F$, so $L$ is recursive. Equivalently, this is the standard theorem that every language recognized by a deterministic finite automaton is a regular language and hence decidable.

For a finite list $(a_0,\dots ,a_{r-1})$ of nonnegative integers, encode its length with the exponent of two and its entries with the following prime numbers: $2^r{\prod }_{j<r}{p}_{j+2}^{a_j+1}$, where $p_i$ is the $i$th prime number. Unique prime factorization recovers both the length and entries. Requiring positive exponents on exactly the prescribed consecutive primes also makes validity decidable. Nesting list descriptors therefore gives a Gödel encoding of deterministic finite automata and other finite syntactic objects.

For a deterministic finite automaton with $N$ states, every accepted word $w$ with $|w|\ge N$ has a decomposition $w=xyz$ such that $|xy|\le N$, $|y|\ge 1$, and $x{y}^{i}z$ is accepted for every integer $i\ge 0$.

A right-linear grammar has productions of the form $A\to wB$ or $A\to w$, where $A,B$ are nonterminals and $w$ is a terminal word, possibly empty. Each right-hand side has at most one nonterminal, at its right end. Such grammars generate exactly regular languages: regard nonterminals as states and expand each terminal word into a finite path to another state or an accepting endpoint. Conversely the transition graph of a deterministic finite automaton gives these productions directly.

The subset construction converts an epsilon-NFA into a deterministic finite automaton. Its states are subsets of NFA states, its initial state is the epsilon closure of the NFA initial state, and every symbol transition is followed by another epsilon closure.