Formal language theory

The shuffle of two formal languages consists of words whose positions can be partitioned into two subsequences, each preserving its order, with the two resulting words belonging to the respective languages. For regular languages, a product-state nondeterministic finite automaton advances exactly one coordinate for each letter. Common letters allow either choice; the powerset construction proves closure.

For a word $u$ and a formal language $L$, the left quotient $u^{-1}L=\{w:uw\in L\}$ is the possible continuation language after the prefix $u$. Two prefixes have the same left quotient exactly when they are Myhill-Nerode equivalent. For a regular language only finitely many distinct left quotients occur.

The padded convolution of words reads two finite words over an alphabet in parallel, extending the shorter with a fresh padding symbol $\#$ until the longer ends. Its length is $\max (|u|,|v|)$. Padding may only occur as a suffix, and a $(\#,\#)$ column is excluded. This encodes synchronous two-tape relations as formal languages over a finite paired alphabet.

A formal language is decidable if a Turing machine halts on every input and correctly determines membership. Equivalently its encoded words form a recursive set. A computably enumerable language requires only a machine that eventually accepts every member; it may run forever on nonmembers.

A word over an alphabet $\Sigma$ is a finite sequence of symbols from $\Sigma$. The empty word has length zero, and ${\Sigma }^{\ast }$ denotes the set of all finite words.

A run of a word over an alphabet is a maximal consecutive block of one repeated letter. For a nonempty word $w$ of length $N$, its number of runs isReplacing a consecutive constant block changes this count only through its boundaries with the neighboring letters.

A border of a word is a nonempty prefix that is also a suffix. The full word is counted as a border; a shorter border records a way in which one occurrence can overlap the next.

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

The Kleene star $L^{\ast }$ of a language $L$ consists of every finite concatenation of words from $L$, including the empty concatenation.

Kleene's theorem states that a language is denoted by a regular expression exactly when it is accepted by a finite automaton.

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

A variable-based grammar has disjoint finite terminal and variable alphabets $\Sigma ,V$, a start variable $S\in V$, and productions $\alpha \to \beta$ in which $\alpha ,\beta \in (\Sigma \cup V{)}^{\ast }$ and $\alpha$ contains at least one variable.

A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated language.

A nonterminal is nonproductive when no word derived from it consists entirely of terminal symbols. Every derivation containing such a symbol therefore fails to produce a word in the generated language.

A right-linear regular grammar has productions of the forms $A\to wB$ and $A\to w$, where $A,B$ are variables and $w$ is a terminal word.

Every sentential form reachable from the start variable of a right-linear grammar is either a terminal word $w$ or $wA$, where $A$ is the unique variable and occurs at the right end.

A variable $A$ is accessible when $S{\Rightarrow }^{\ast }wA$ for some terminal word $w$.

A variable $A$ is looping when $A{\Rightarrow }^{\ast }wA$ for some terminal word $w$ through a nonempty derivation.

A variable $A$ is terminable when $A{\Rightarrow }^{\ast }w$ for some terminal word $w$.

If a finite right-linear grammar generates an infinite language, some variable is accessible, looping, and terminable. It is the repeated variable on a sufficiently long accepting derivation.

For grammars $G=(\Sigma ,V,P,S)$ and $G^{\prime }=(\Sigma ,V^{\prime },P^{\prime },S^{\prime })$ with disjoint variable sets, introduce a new variable $S_0$ and setIf both input grammars are variable based, then $L(H)=L(G)L(G^{\prime })$.

Retain every production $\alpha \to \beta$ of $P$ whose right-hand side contains a variable, replace every production $\alpha \to w$ with $w\in {\Sigma }^{\ast }$ by $\alpha \to w{S}^{\prime }$, include $P^{\prime }$, and use $S$ as start variable. If $G$ and $G^{\prime }$ are right-linear, the resulting grammar is right-linear and generates $L(G)L(G^{\prime })$.

The regular construction relies on a regular derivation having exactly one terminal rule, at its end. In a general variable-based grammar several variables may each use terminal productions, so replacing every such production can introduce several copies of the second start variable.

Even if both input grammars are regular, the added production $S_0\to S{S}^{\prime }$ has two variables on its right-hand side and therefore need not be a regular production.

The empty word is the unique word of length zero. It is the identity element for concatenation.

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

A context-free grammar consists of terminal and nonterminal alphabets, a start symbol, and productions whose left side is one nonterminal. A derivation records the order of substitutions, while a parse tree records their hierarchical structure, so several derivations can represent one parse tree.

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.

A nonterminal symbol is a grammar symbol that may be replaced by a production and need not occur in a completed word.

A terminal symbol belongs to the alphabet of completed words and is not replaced by a grammar production.

A production rule specifies a permitted replacement during a grammar derivation. In a context-free grammar it has the form $A\to \alpha$, with one nonterminal $A$ on the left.

A sentence of a grammar is a terminal word derivable from its start symbol.

A grammar derivation is a finite sequence of words in which each step replaces one occurrence of a production's left side by its right side. A leftmost derivation always replaces the leftmost available nonterminal.

A parse tree places the start symbol at its root, the symbols on the right side of a production at the children of its left-side nonterminal, and terminal symbols at its leaves. Reading the leaves from left to right gives the tree's yield.

Two grammars are equivalent when they generate the same formal language.

Two grammars over a common terminal alphabet are isomorphic when a bijection between their nonterminal alphabets maps one start symbol to the other and maps their productions bijectively after being extended to fix every terminal symbol. Isomorphic grammars are equivalent.

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, with $A,B,C$ nonterminals and $a$ a terminal. If the empty word belongs to the language, one commonly also permits the exceptional rule $S\to ϵ$ under the usual restriction on the start symbol.

An epsilon production is a grammar production whose right-hand side is the empty word.

A unit production replaces one nonterminal by one nonterminal and emits no terminal symbols.

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

A Chomsky-normal-form parse tree for a word of length $n\ge 1$ has $n$ terminal productions and $n-1$ binary productions. Every derivation represented by the tree therefore has exactly $2n-1$ steps.

The CYK algorithm decides membership in a context-free language given by a grammar in Chomsky normal form. It records, for every substring, the nonterminals that derive that substring and combines adjacent substrings using binary productions. For a word of length $n$ and a fixed grammar, it runs in $O(n^3)$ time.

Weak Chomsky normal form additionally permits ternary productions $A\to BCD$. Compressing a two-step pattern $A\to BE$, $E\to CD$ into $A\to BCD$ preserves its generated yields whenever the intermediate variable has no other role, and saves one derivation step each time the pattern is used.

The productions $S\to 0S0\mid 1S1\mid 00\mid 11$ generate exactly the nonempty binary palindromes of even length.

The intersection of a context-free language with a regular language is context-free, because a pushdown automaton and a finite automaton can be run in product.

If context-free grammars with disjoint nonterminal alphabets have start symbols $S_1,S_2$, adjoining a new start symbol and the production $S\to S_1{S}_2$ gives a context-free grammar for the concatenation of their languages.

If a context-free grammar for $L$ has start symbol $S$, adjoining a new start symbol $S_0$ and productions $S_0\to ϵ\mid S{S}_0$ gives a context-free grammar for the Kleene star $L^{\ast }$.

Every context-free language over a one-symbol alphabet is a regular language. Equivalently, the set of word lengths of a unary context-free language is ultimately periodic. This follows, for example, from the one-dimensional case of Parikh's theorem.

A context-free grammar can enforce sums such as $0^n{1}^m{0}^{n+m}$ by nesting one matched terminal pair for each independent count.

The languageis context-free. The grammarnests the $a,d$ dependency around the $b,c$ dependency.

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$.

The language $\{0^p{1}^p:p\text{ is prime}\}$ is not context-free. For a proposed pumping length, start with a larger prime $p$. Pumping unequal numbers of zeros and ones breaks equality; if the positive changes are equal to $d$, pumping with exponent $p+1$ gives the composite common block length $p(1+d)$.

For a word consisting of three long constrained blocks, a pumpable window shorter than each block cannot alter both outer blocks; pumping then breaks a required three-way count relation.

A pumping length is a threshold beyond which every word in the language has a decomposition satisfying the conclusion of the relevant pumping lemma.

The language $\{a^{m^2}{b}^{m^2}:m\ge 0\}$ is not context-free. Pump a word with both block lengths $p^2$. Unequal changes to the blocks destroy equality; an equal positive change $d\le p$ makes both lengths $p^2+d$, which lies strictly between consecutive squares $p^2$ and $(p+1{)}^2$.

A finite-state automaton recognizes a formal language by updating one of finitely many states as it reads each input symbol.

A dead state of a finite automaton has no path to an accepting state. In a complete deterministic finite automaton, all dead states may be merged into one rejecting sink without changing the accepted formal language.

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.

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.

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 deterministic finite automaton has finitely many states and one transition for each state-symbol pair.

For a transition function $\delta :Q\times \Sigma \to Q$, defineThe accepted language is $\{w:\hat{\delta }(q_0,w)\in F\}$.

A state is accessible when some input word takes the initial state to it. Removing inaccessible states preserves the accepted language.

Two states are indistinguishable when every continuation is accepted from both or rejected from both. Distinguishable states admit at least one suffix with different acceptance outcomes.

Indistinguishability is a right-invariant equivalence relation. The quotient has states $[q]$, transition $[q]\mapsto [\delta (q,a)]$, initial state $[q_0]$, and accepting classes represented by accepting states. It accepts the original language and has no two distinct indistinguishable states.

A deterministic automaton is irreducible when every state is accessible and every pair of distinct states is distinguishable.

An irreducible deterministic automaton has the fewest states among deterministic automata for its language and is unique up to isomorphism. Its states are the Myhill--Nerode classes.

The canonical residual automaton of a regular language has its distinct left quotients of a formal language as states, initial state $L$, accepting states those containing the empty word, and letter transition $R\mapsto a^{-1}R$. It is a complete minimal deterministic finite automaton; every other complete minimal deterministic finite automaton for that language is isomorphic to it.

In a minimal deterministic finite automaton accepting a finite language, any state lying on a nonempty directed cycle is the unique rejecting sink state. It cannot reach an accept state, since traversing the cycle arbitrarily many times would produce infinitely many accepted words. Every state reachable from it also rejects every continuation, so minimality forces all such states to be the same state.

For a positive integer $m$, binary strings can be tested for divisibility by $m$ with residue states $0,\dots ,m-1$ and transitionThe initial and accepting residue is zero. For $m=7$, all seven states are reachable and pairwise distinguishable, so this automaton is minimal.

An accessible automaton over one letter consists of a directed tail entering one directed cycle. Its minimal quotient is obtained by merging positions having the same future binary acceptance sequence.

To recognize prescribed parities of several symbol counts, use one state for each tuple of parities. Reading a tracked symbol toggles its coordinate and leaves all other coordinates unchanged. For two tracked symbols this gives four states indexed by ${\mathbb{Z}}_2^2$.

To recognize words having at most $m$ consecutive copies of a symbol, use states $0,1,\dots ,m$ recording the current run length and one rejecting sink. Another symbol resets the run length to zero, while the $(m+1)$st consecutive copy enters the sink.

A nondeterministic finite automaton assigns a set of possible successor states to each state-symbol pair and accepts when at least one run ends in a final state.

An epsilon-NFA is a nondeterministic finite automaton that may traverse transitions labelled $ϵ$ without consuming an input symbol.

The epsilon closure of a state set $S$ consists of every state reachable from $S$ using zero or more epsilon transitions.

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.

Without epsilon transitions, defineA word is accepted when the set reached from the initial state meets the final set.

For $w=a_0\cdots a_{n-1}$, a witnessing sequence from $p_0$ to $p_n$ satisfies $p_{i+1}\in \Delta (p_i,a_i)$. Induction on word length shows that $q^{\prime }\in \hat{\Delta }(q,w)$ exactly when such a sequence runs from $q$ to $q^{\prime }$.

The powerset construction turns an NFA with state set $Q$ into a DFA with state set $\mathcal{P}(Q)$, transitionand accepting subsets that meet the NFA final set.

In the convention used here, a Brzozowski NFA has one final state, every state can reach it, and each word labels a path to it from exactly one starting state.

For distinct accessible subset states, choose a state in their symmetric difference. A word taking it to the unique final state accepts from one subset; uniqueness of the starting state prevents acceptance from the other. Thus the accessible part of the subset automaton is irreducible.

A language is regular exactly when it is accepted by a finite automaton, or equivalently has finitely many Myhill-Nerode classes.

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$.

Over an alphabet containing $a,b$, the language $\{w^n:n\ge 2\}$ is not regular language. Intersecting it with the regular language $a^{+}b{a}^{+}b$ gives exactlywhich fails the pumping lemma for regular languages.

Let $K\subseteq \mathbb{N}$ be undecidable andPumping its first symbol always stays in $L$, so it satisfies the pumping lemma with pumping length one. Yet $L\cap a{b}^{\ast }=\{a{b}^n:n\in K\}$ is not regular, because a finite automaton for it would decide $K$.

The base-two representations of powers of two form the regular language $10^{\ast }$. Their base-ten representations are not regular. Pumping a fixed decimal substring of length $d$ would produce powers of two $a_i$ satisfying $a_{i+1}-10^d{a}_i=C$. After division by $a_i$ and passage to large $i$, integrality would force a power of two to equal $10^d$, contradicting unique factorization.

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

For a language $A\subseteq {\Sigma }^{\ast }$, defineThis is a right congruence, and its equivalence classes are the states of the minimal deterministic finite automaton for $A$.

A language class is closed under an operation when applying that operation to members always produces another member of the class.

A language is computably enumerable when a machine recognizes its members, possibly running forever on nonmembers.

The halting set is computably enumerable but undecidable, and its complement is not computably enumerable.

A machine's halting times admit a total computable function as a bound on all inputs in its domain if and only if that domain is a computable set. A bound decides the domain by finite simulation; conversely, a domain decider allows returning zero outside the domain and the exactly simulated halting time inside it. In particular every machine computing a total computable function has an exact computable running-time function, while nontotal machines may or may not have total bounds.

The halting set of a Turing machine $T$ is the set of inputs on which it eventually halts. For a deterministic machine with a designated terminal state, eventual halting is invariant along every transition edge, even when that edge is traversed backwards. This observation justifies passing from forward computations to symmetric equality derivations in a semigroup presentation.

For an effective enumeration of unary partial computable functions, the diagonal halting set isEquivalently, for an enumeration $W_e$ of computably enumerable sets, $K=\{e:e\in W_e\}$.

Every recursively enumerable set many-one reduces to the diagonal halting set. If a program halts exactly on $X$, the S-m-n theorem produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. ThenConversely, a computable preimage of a recursively enumerable set is recursively enumerable.

If $0\notin K$, thendiffers from $K$, while the computable map $n\mapsto 2n+1$ proves $K{\le }_{m}S$.