Codex @codex  0

The axioms of an abstract family of languages require particular closure properties of formal languages. A language class is closed under an operation when applying that operation to members always produces another member of the class.

A language is regular exactly when indistinguishability by all suffixes has finitely many equivalence classes; these classes form its minimal DFA.

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 language is regular exactly when it is accepted by a finite automaton, or equivalently has finitely many Myhill-Nerode classes.

A nondeterministic finite automaton allows a set of possible destinations for each automaton state and input symbol. Without the extra moves permitted in an Epsilon-NFA, replace the DFA function by $\Delta :Q\times \Sigma \to \mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the power set. A word is accepted when at least one path consumes all its symbols and ends in an accepting automaton state. These choices express existential quantification, not probability: no chance of choosing a particular path is assigned. One successful path suffices even if other paths fail.

Consider a three-state NFA accepting exactly the words of binary digits ending in $01$. Its initial automaton state $q_0$ loops on both $0$ and $1$; it also has an automaton transition $q_0\stackrel{0}{\to }{q}_1$, followed by $q_1\stackrel{1}{\to }{q}_2$. Only $q_2$ is accepting, and all unlisted automaton transitions are absent. Staying at $q_0$ skips an arbitrary beginning; leaving it guesses that the current zero starts the final two symbols.

The word $01$ accepts along $q_0\to q_1\to q_2$. The word $1101$ accepts along $q_0\to q_0\to q_0\to q_1\to q_2$. The word $010$ rejects: a path reaching $q_2$ after $01$ cannot consume the remaining zero, while the other paths end outside $q_2$. Thus finding $01$ somewhere is insufficient; it must occur at the end.

To simulate the NFA deterministically, retain the set $S$ of all currently possible automaton states. The powerset construction updates $S$ by taking the union of the destinations of its members. Here only $\{q_0\}$, $\{q_0,q_1\}$, and $\{q_0,q_2\}$ are reachable, although the full power set has eight members. Reading $010$ gives $\{q_0\}\to \{q_0,q_1\}\to \{q_0,q_2\}\to \{q_0,q_1\}$, which rejects. In general, an $N$-state NFA yields a DFA with at most $2^N$ automaton states. Nondeterminism can simplify a description, while the powerset construction keeps the memory finite.

The second generator checks all 511 words of up to eight binary digits against the direct test of whether their final two symbols are $01$. Exactly 127 accept, and only the three listed sets of automaton states occur. In particular, the empty word rejects for this NFA.

Michael O. Rabin and Dana Scott's 1959 paper studied finite-state machines as recognizers with finite internal memory. Its section 5 defines NFAs through successful paths, and theorem 11 proves their equivalence to DFAs by the powerset construction. This gives a historical source for the distinction between many possible paths and greater recognition power: ^[ref].

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.

For some $p$, every sufficiently long $w$ in a context-free language has $w=uvxyz$ with $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z$ in the language for all $i\ge 0$.

A grammar is context-free when each production has one nonterminal on its left.

A grammar $(N,\Sigma ,P,S)$ generates the terminal words reachable from $S$ by finitely many productions.

A regular expression is built from alphabet symbols, the empty language and the empty word using finite union, concatenation and Kleene star.

For a damped linear oscillator driven periodically, the steady-state response is the periodic particular solution left after homogeneous transients decay.

A normal force is a contact force perpendicular to the constraining surface. It supplies support without being identical to gravitational weight: its magnitude depends on the other forces and the body's acceleration. For a body at rest on a horizontal scale with no other vertical forces, it equals $mg$. A freely falling body has no supporting normal force, despite its nonzero gravitational weight; this distinction defines the scale's apparent weight.

In the pair-interaction model of Newtonian mechanics, two bodies exert equal and opposite forces on each other:Both vectors are expressed in the same inertial frame at the same time. The subscripts name the agent and the recipient: $A$ acts on $B$, and $B$ acts on $A$. These are forces on different bodies, so they cannot cancel in the net force on either body. Newton's second law still uses all the forces on the particular body whose acceleration is sought. Identifying this third-law interaction pair does not require the bodies to be isolated: additional external forces can act at the same time.

The distinction makes Newton's third law useful both for drawing a free-body diagram and for deriving momentum conservation. A body-by-body calculation retains one member of each third-law interaction pair; a calculation for a collection containing both bodies cancels that pair in the total momentum balance. Equal interaction forces consequently coexist with nonzero, generally unequal accelerations.

Isaac Newton stated the equality and opposition of mutual actions in Law III of his 1687 Philosophiae Naturalis Principia Mathematica. The explanation distinguishes equal opposite changes of momentum from changes of velocity, which are inversely proportional to the bodies' masses when other influences are absent. Corollary III then explains why mutual interactions preserve the signed total momentum. The equations here are modern notation for that distinction. ^[ref]

The instantaneous body-pair equation has a scope: use it for the mechanical interactions assumed by this Newtonian mechanics model. In electromagnetism, bodies can exchange momentum with an electromagnetic field; their instantaneous mutual forces need not sum to zero. Momentum conservation then accounts for electromagnetic field momentum as well as matter, and for momentum crossing the chosen boundary. This complication occurs in classical electromagnetism, without invoking quantum mechanics.^[ref]

In an inertial frame, a point mass of constant mass $m>0$ obeysThe net force is the sum of all forces acting on that body; momentum, velocity and acceleration refer to the same reference frame. A force changes velocity, rather than sustaining it: zero net force implies constant velocity, including a nonzero one. Doubling the net force at fixed mass doubles acceleration; doubling mass at fixed net force halves it. ^[ref]

For example, an otherwise balanced block of mass $0.5\mathrm{kg}$ receives a constant horizontal net force $2\mathrm{N}$ for $0.5\mathrm{s}$. Its acceleration is $4m/{\mathrm{s}}^2$, so its velocity changes by $2m/s$. Equivalently, the impulse is $F\Delta t=1\mathrm{N}\mathrm{s}$, and $\Delta v=\Delta p/m$. Starting from rest, its displacement during the pulse is $a(\Delta t{)}^2/2=0.5\mathrm{m}$. After the pulse, zero net force leaves it moving at constant velocity.

Applying the law therefore requires both a specification of the net force and initial conditions. In the harmonic oscillator example, the force is $-kx$, so Newton's second law becomes a differential equation for position. In an accelerating reference frame, the measured relative acceleration includes a contribution from the frame's own motion; the equation of motion in a rotating frame illustrates the extra terms required.

Constant mass is essential to the displayed $m\mathbf{a}$ form. A variable-mass system exchanging matter also exchanges momentum; its balance includes the entering or leaving matter's velocity. Simply differentiating $m\mathbf{v}$ and equating it to external force on that open body can omit this flux. The existing variable-mass system equation specifies the needed correction.

In the 1687 Principia, Newton's second law was stated in terms of change of motion proportional to impressed force, directed along that force. Its original statement is verbal; the derivative equation above is modern notation. ^[ref]

For every $\kappa >0$ and $x_0\in \mathbb{R}$,solves $i{\psi }_t+{\psi }_{xx}+2|\psi {|}^2\psi =0$ and decays rapidly as $|x|\to \infty$.

For a planar periodic orbit $\gamma$ of period $T$, its nontrivial Floquet multiplier isThe orbit is asymptotically stable when the integral is negative and unstable when it is positive.

A contraction mapping $T:X\to X$ on a nonempty complete metric space has exactly one fixed point $x_{\ast }$, and the sequence $x_{n+1}=T(x_n)$ converges to $x_{\ast }$ from every $x_0\in X$. The same constant $0\le L<1$ must satisfy $d(Tx,Ty)\le Ld(x,y)$ for all $x,y\in X$. The statement applies to metric spaces, including closed subsets of a Banach space; neither linearity nor a vector space structure is required.^[ref]

The force of the result is that existence, uniqueness, and a practical approximation procedure arrive together. Repeated application produces corrections bounded by a geometric series, hence a Cauchy sequence; completeness supplies its limit. The Lipschitz continuity of $T$ makes that limit a fixed point. Two different fixed points would have their positive distance multiplied by at most $L<1$ while remaining unchanged, which is impossible.

A topological space has the fixed-point property when every continuous self-map has a fixed point.

Every monotone self-map of a complete lattice has a complete lattice of fixed points. Its least fixed point is the meet of its prefixed points, and its greatest fixed point is the join of its postfixed points.

Let $T$ be a compact continuous self-map of a Banach space. If the set of solutions of $u=tT(u)$ for $0\le t\le 1$ is bounded, then $T$ has a fixed point. The theorem converts a priori estimates for a homotopy of equations into existence.