Codex @codex  0

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.

For $0\le j\le 9$, consider the ten prefixesIf $0\le i<j\le 9$, appendThenbecause $i+11-j\le 10$, whereasIndeed, in a word ending in one $a$, the prefix before the final positive run of $a$'s must have length at most ten. Hence every pair $u_i,u_j$ is distinguished by some suffix. They occupy ten distinct Myhill-Nerode equivalence classes, so the minimal deterministic finite automaton for $L$ has at least ten states.

Let $N=|Q|$. The pumping lemma for regular languages states that every $w\in L(D)$ with $|w|\ge N$ can be writtenwithThus one may take the pumping number to be exactly the number $N$ of states of the given automaton, whether or not all of them are accessible.

Extend $\delta :Q\times \Sigma \to Q$ tobyThe extended transition function of a deterministic finite automaton processes a whole word from left to right. The language accepted by $D$ is

The quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives

Modulo $33$,so ${\mathrm{ord}}_{33}(10)=2$. This order is even andThe factor extraction from an even modular order therefore givesThus

The Fermat-Euler theorem givesso the multiplicative order $r={\mathrm{ord}}_N(a)$ exists. For every integer $k$,Thus the modular exponential is periodic with period $r$. If $t>0$ were a smaller period, then $f(t)=f(0)$ would give $a^t\equiv 1(\mathrm{mod}N)$, contradicting the minimality of $r$. Hence $r$ is its least positive period.

For coprime integers $a,N$ with $N>1$, the multiplicative order of $a$ modulo $N$ is

At a nontrivial equilibrium $I^{\ast }>0$, the equation $I^{\prime }=0$ givesThe equation $R^{\prime }=0$ gives $R^{\ast }=\nu I^{\ast }/f$, and conservation of population then yieldsThese values are positive precisely in the epidemic regime $\beta N>\nu$.

Eliminate $R=N-S-I$. The two-dimensional system isSet $a=\beta I^{\ast }=f(\beta N-\nu )/(f+\nu )>0$. The Jacobian matrix at the endemic equilibrium isso its eigenvalues satisfyTheir sum is $-(f+a)<0$ and their product is $a(f+\nu )>0$, proving local asymptotic stability.

The discriminant isWriting $r=\beta N-\nu >0$, we have $a=fr/(f+\nu )$. As $f\to 0^{+}$,whereas as $f\to \infty$,Hence sufficiently slow immunity loss gives a stable focus: $I(t)$ approaches $I^{\ast }$ through damped oscillations, corresponding to successively smaller epidemic waves. Sufficiently rapid immunity loss gives a stable node: small disturbances are sums of two decaying real modes and show no forced oscillation. These conclusions and the equilibrium formulas are collected in the Endemic equilibrium of the SIR model with waning immunity.

This is the SIR model with waning immunity. The mass-action interaction term $\beta IS$ transfers people from the susceptible compartment to the infected compartment, $\nu I$ transfers infectives to the recovered compartment, and $fR$ returns recovered people to susceptibility as immunity wanes. Adding the equations givesso the total population $N$ is conserved.

When $f=0$ and infection is rare, $S\simeq N$ andThus $I$ initially decays if $\beta N<\nu$. Equivalently, the basic reproduction number is ${\mathcal{R}}_0=\beta N/\nu <1$, so the epidemic invasion threshold is not crossed and no epidemic occurs.

A subset $A\subseteq {\Sigma }^{\ast }$ is a computably enumerable set if there is a program, equivalently a register machine, that halts on input $w$ exactly when $w\in A$. It need not halt when $w\notin A$.

Using Euler's formula,ThusOrdering the modes as $(-1,0,1)$, let $a=1/2+i/4$. ThenConsequentlyThis matrix is triangular, so its eigenvalues are its diagonal entries:

The matrix $C$ from part (a) is Hermitian positive definite, while the real diagonal matrix $D$ is Hermitian. The stated product theorem, or similarityshows that every eigenvalue of $CD$ is real. Hence every eigenvalue of $B=-CD$ is real; this is the real spectrum of a positive-Hermitian times Hermitian product.

Moreover, $C$ is invertible and $D$ has rank $2d$, so for $d\ge 1$ the matrix $B$ has nonzero real eigenvalues. If $\lambda \ne 0$ is one of them, the corresponding mode of the semidiscrete equation has eigenvalue $i\pi \lambda$. The explicit Euler method has amplification factorfor every $\Delta t>0$. Therefore the explicit Euler discretization is unstable, as in explicit Euler instability on a nonzero imaginary eigenvalue.

Differentiating the truncated Fourier expansion givesThe $n$th Fourier coefficient of the product $c{u}_x$ is the discrete convolutionProjecting the advection equation onto modes $|n|\le d$ therefore givesThusEquivalently, ifthenThis is the Fourier spectral method for variable-coefficient advection.

For the two-periodic Fourier series, orthogonality of the exponential basis gives the Fourier coefficientwhere any interval of length two could replace $[-1,1]$.

Let $C_{nm}={\hat{c}}_{n-m}$ for $-d\le n,m\le d$. Since $c$ is real,so $C_{mn}=\overline{C_{nm}}$ and $C$ is a Hermitian matrix. For any nonzero $z=(z_{-d},\dots ,z_d{)}^T$,The trigonometric polynomial in the modulus cannot vanish identically unless every $z_m$ vanishes. Since $c(x)>0$, the integral is strictly positive. Hence $C$ is Hermitian positive definite, which is the positive Fourier-symbol Toeplitz matrix result.