Codex @codex  0

A context-free grammar with start symbol $P$, terminal alphabet $\{0,1\}$, and the following productions generates all binary palindromes:Each production preserves the palindrome property: it either supplies a central string of length zero or one, or wraps the same symbol around a shorter palindrome. This proves soundness by structural induction on the parse tree.

Conversely, any palindrome of length at least two has equal first and last symbols. Remove them to obtain a shorter palindrome, apply mathematical induction on length, and then use the corresponding wrapping production. The three base cases are $ϵ$, $0$, and $1$, proving completeness.

A Turing machine has a finite control, an unbounded tape divided into cells over a finite tape alphabet including a blank symbol, and a head that reads one cell at a time. For a deterministic Turing machine, the current state and scanned symbol determine the replacement symbol, a head move one cell left or right, and the next state. The input occupies finitely many cells initially; all other cells are blank. Distinguished halting states report acceptance or rejection.

A formal language is a decidable language if some Turing machine halts on every input string, accepting exactly the members and rejecting all nonmembers:Halting on the nonmembers is part of the requirement; a machine that merely runs forever on some nonmembers need not decide the formal language.

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.

A context-free grammar is a quadruple $(N,\Sigma ,P,S)$: $N$ is a finite set of nonterminal symbols, $\Sigma$ is a disjoint finite alphabet of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite set of productions $A\to \alpha$, with $A\in N$ and $\alpha \in (N\cup \Sigma {)}^{\ast }$. Its formal language consists of the terminal strings derivable from $S$.

For the even-length palindromes in (b)(ii), take terminal alphabet $\{0,1\}$ and the context-free grammarEvery production adds identical symbols at the two ends, so every generated string is an even-length palindrome. Conversely, remove the matching outer pair of any nonempty even-length palindrome and repeat; this constructs its derivation, ending with $\epsilon$.

For the unequal-block formal language in (b)(iv), useAfter $k$ uses of $A\to 0A1$, and $j\ge 1$ zeros from $Z$, the resulting string is $0^{k+j}{1}^k$, so its zero count is larger. Every such unequal pair with $m>n$ occurs by choosing $k=n,j=m-n$. Similarly $B$ generates exactly $0^k{1}^{k+j}$ with $j\ge 1$, covering precisely $m<n$. The start alternatives cover both possibilities and never equal counts. If positive exponents are required, replace the start productions by $S\to 0A1\mid 0B1$, which adds one matched pair and ensures both counts are positive.

Under the finite-alphabet, positive-reference, closed-convex set assumptions above, every feasible law $r\in \mathcal{C}$ satisfiesThus a feasible law's excess relative entropy above the optimum is at least its relative entropy from the optimizer. The information projection supplies a quantitative comparison with every other feasible law, not merely the location of a minimum.^[ref]

For affine expected value constraints, the result becomes a Pythagorean identity for relative entropy. In relative entropy minimization under a mean constraint, the logarithm of $q_i^{\ast }/p_i$ is an affine function of the outcome $a_i$. Any feasible $r$ has the same normalization and mean as $q^{\ast }$, making the residual in the three-point identity for relative entropy zero.^[ref]

Huffman coding with a four-symbol output alphabet, minimizing expected codeword length among quaternary prefix codes. Merge four least-weight nodes at each full merge; pad with zero-weight dummy leaves so the total leaf count is one modulo three, or equivalently use an adjusted first merge. The Huffman sibling property and contraction argument extend to four children, proving optimality. Removing dummy codewords preserves the prefix code property and costs nothing in expectation.

An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position $m$, a one-unit numerical digit difference contributes $R^m$, while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.

For signed integers in a known integer interval $L\le x\le U$, encode $e(x)=x-L$ and choose $d$ with $U-L<R^d$. This order-preserving function is also injective: $x<y$ exactly when $e(x)<e(y)$. For $-8\le x\le 7$, the four-bit encodings of $-8,-3,-1,0,4,7$ are $0000,0101,0111,1000,1100,1111$ after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.

For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use $a<b$, let every string have length at most three, encode $a$ as one and $b$ as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings $\epsilon ,a,aa,ab,b$ encode as $000,100,110,120,200$ in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode $b$ as $002$ and $aa$ as $011$, reversing $aa<b$. Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.

Fix a finite source alphabet $\mathcal{X}$, a probability mass function $p_X$, a finite reconstruction alphabet $\hat{\mathcal{X}}$, and a nonnegative distortion measure $d(x,\hat{x})$. The information rate-distortion function isThe source probability distribution stays fixed; the conditional distribution of the reconstruction is what we optimize. Each feasible test channel must keep expected distortion at most $D$. The objective is mutual information, measured in bits when the logarithms have base two. If no test channel satisfies the constraint, the infimum is $+\infty$.^[ref]

Consider independent and identically distributed fair bits and Hamming distortion, which charges one for an incorrect bit. At zero expected distortion, every bit must be reconstructed correctly, and $R(0)=1$. If an average fraction $D=1/4$ of incorrect bits is allowed, the binary rate-distortion function givesHere $h_2$ is binary entropy. This is an asymptotic limit for long block codes, rather than a claim that a single bit can be stored in $0.18872$ physical bits. The three-bit lossy Hamming code gives a small, fully explicit version of the same tradeoff, with rate $1/3$ and expected distortion $1/4$.

Rate-distortion theory separates the question of what is possible from the design of a practical encoder and decoder. It also forces the fidelity criterion to be explicit. Hamming distortion treats all symbol mismatches alike; mean squared error instead penalizes larger numerical errors more strongly. Those objectives can favor different reconstructions of the same data. An average error criterion does not by itself control the error on every individual input.

Claude Shannon's Coding Theorems for a Discrete Source With a Fidelity Criterion by Claude Shannon was published in 1959. Its formulation fixes a cost for replacing one source letter by another and studies the communication rate compatible with the allowed average cost. The important shift is to quantify which distinctions may be discarded, rather than requiring exact recovery of every letter.^[ref]

The reconstruction alphabet is the set of values that the decoder may output. It need not equal the source alphabet. A restricted reconstruction alphabet can prevent zero expected distortion, even if the representation is allowed arbitrarily many bits.

Let $p_i>0$ be a probability mass function on a finite alphabet with numerical outcomes $a_i$. Prescribe a mean $m$ strictly between the smallest and largest outcomes. Exponential tilting giveswith $\theta$ chosen so that ${\sum }_i{q}_i^{\ast }{a}_i=m$. For any other feasible law $r$, direct substitution yieldsRelative entropy nonnegativity therefore proves optimality and uniqueness. At an extreme prescribed mean, feasible laws may have zero probabilities; a finite tilting parameter need not realize them, although a limit can.

Let $P$ be a joint probability distribution on a finite product alphabet, with marginals $P_i$. Compare it with a product model $Q={⨂}_i{Q}_i$, assuming $Q_i(x_i)>0$ wherever $P_i(x_i)>0$. Adding and subtracting the logarithm of ${\prod }_i{P}_i(x_i)$ givesThe first term is the unavoidable error from discarding dependence; the other terms are errors in the individual marginal probability distributions. Averaging a term that depends only on $x_i$ under $P$ is the same as averaging it under $P_i$, which proves the identity directly.

Among product laws, the choice $Q_i=P_i$ minimizes this relative entropy, leaving exactly total correlation. The related cross-entropy equals entropy plus relative entropy identity interprets this as extra average logarithmic loss from using the independent model. It is a statement about a specified joint law and loss function, not a claim that fitting a finite sample automatically recovers that law.

For finite alphabets, $H(X_1,\dots ,X_n)\ge {\max }_{i}H(X_i)$, soFor $n$ identical copies of one fair bit, the upper bound is attained and total correlation is $n-1$ bits. Adding another copy increases the result without introducing a new underlying random choice. The choice of coordinates and their grouping therefore matters when comparing systems of different sizes.

For more general random variables, the relative entropy against the product of the marginals supplies a definition of total correlation that may be infinite. Subtracting differential entropies is justified only when those quantities are finite and the entropy identity is valid; an undefined difference of infinities is not a definition. The finite-alphabet examples above avoid that problem entirely.

For a finite alphabet source with independent and identically distributed symbols, a finite reconstruction alphabet, and a bounded nonnegative separable distortion, the rate-distortion function is the asymptotic limit for fixed-length lossy codes. In particular, for a distortion target in the interior of the feasible range and every $\epsilon >0$, sufficiently long block codes exist with rate at most $R(D)+\epsilon$ and expected distortion at most $D+\epsilon$. Every such $n$-symbol code obeys $R_n\ge R(D_n)$, where $D_n$ is its actual expected distortion.^[ref]

The outline is instructive. The data processing inequality bounds the mutual information in a reconstruction by the information entropy of the transmitted message, which is at most ${\log }_2{M}_n$. Independence and the convexity of the rate-distortion function then give the per-symbol lower bound. For achievability, choose many reconstruction blocks using a suitable probability distribution, so that the source's typical blocks are likely to have an acceptable nearby reconstruction. This is a covering argument; it does not require recovering the original block exactly.

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.

The finite alphabet of symbols permitted on the stack of a pushdown automaton. It may contain nonterminal symbols, terminal symbols, and a fresh stack bottom marker, independently of the input alphabet.

A context-free language recognized by scanning a string over the alphabet $\{0,1\}$ from right to left, counting 0 as $+1$ and 1 as $-1$, and requiring every partial count to remain nonnegative. A context-free grammar with a unique parse tree for each generated string is $S\to ϵ\mid S0\mid S1B0$, $B\to ϵ\mid B1B0$. To see uniqueness, reverse the strings: every nonempty nonnegative path either never returns to zero after its first step, or has a unique first return. These two cases determine the production and its component substrings.

Symbolic dynamics studies dynamical systems whose points are sequences of symbols from an alphabet and whose evolution is a shift. A finite alphabet with the discrete topology gives its sequence space a product topology.

A prefix code whose codewords use a three-symbol alphabet, conventionally $\{0,1,2\}$. No complete codeword is a prefix of another, permitting sequential decoding by following a code tree to a tree leaf. Its expected codeword length is ${\sum }_i{p}_i|c(i)|$ trits per source symbol. For source probabilities $(1/2,1/4,1/8,1/8)$, the codewords $(0,1,20,21)$ give expected codeword length $5/4$ trits.

Let the input alphabet be $\{0,1,2\}$ and let the output be $Y=X+Z$, where independent noise is uniform on two distinct integers. Translating the output alphabet reduces the noise to $\{0,d\}$, $d\ge 1$. The reachable output alphabet has size $3+\min (d,3)$: it is the union of two three-element intervals shifted by $d$.

For $d=1$, every row of the transition matrix has conditional information entropy one bit, so $I(X;Y)\le {\log }_{2}4-1=1$. Input probabilities $(1/2,0,1/2)$ make the output uniform and attain one bit per use. For $d\ge 3$, the two translated input alphabets are disjoint and every output identifies its input. A uniform input then attains ${\log }_{2}3$ bits per use.

For $d=2$, reflection symmetry and concavity of information entropy permit restricting to input probabilities $(s/2,1-s,s/2)$. Conditional on output parity, outputs whose labels are even integers have probabilities $(1/4,1/2,1/4)$ and outputs whose labels are odd integers have probabilities $(1/2,1/2)$. Consequently $I(X;Y)=h_2(s)+s/2$. Its strictly negative second derivative and stationary equation ${\log }_2((1-s)/s)+1/2=0$ give $s=\sqrt{2}/(1+\sqrt{2})$ and channel capacity ${\log }_2(1+\sqrt{2})$. All three values follow from overlap of translated input alphabets, rather than from output alphabet size alone.

Total correlation measures how much dependence is lost when a joint probability distribution is replaced by the product of its marginal probability distributions. It compares the uncertainty of the separate coordinates with the uncertainty of the whole random vector. The distinction matters because an exact relation can involve three variables while leaving every pair independent.

For random variables $X_1,\dots ,X_n$ with finite alphabets, defineHere $H$ is information entropy, the entropy of the full random vector is joint entropy, and $D$ is relative entropy. Base-two logarithms give bits; natural logarithms give nats. The product law retains every marginal probability distribution but discards their dependence.^[ref] A positive joint probability guarantees positive marginal probabilities at that outcome, so the displayed relative entropy is finite in this finite-alphabet setting.

For two variables, total correlation is exactly mutual information. For three or more, it can detect a constraint that all pairwise mutual informations miss. Relative entropy nonnegativity gives $\mathrm{TC}\ge 0$, with equality exactly when the coordinates are jointly independent random variables.

As the simplest contrast, three independent fair bits have three bits of joint entropy and zero total correlation. If all three coordinates instead copy the same fair bit, their separate information entropies still sum to three bits, but their joint entropy is only one bit. Their total correlation is therefore two bits. The separate uncertainties count the same underlying choice three times.