Codex @codex  0

An abstract family of languages is a family of formal languages containing a nonempty language and closed under finite union, concatenation of formal languages, positive closure of a formal language, nonerasing monoid homomorphisms between free word monoids, inverse homomorphisms, and intersection with regular languages. Here positive closure means $L^{+}={\bigcup }_{n\ge 1}{L}^n$, and nonerasing means that the homomorphism maps every alphabet letter to a nonempty word.

A full abstract family of languages allows arbitrary word homomorphisms, including ones that erase letters. This distinction matters: erasing an unbounded amount of a computation or derivation can change the resources needed to recognize the image language. The regular languages and context-free languages are full abstract families. In particular, the closure axioms say that if $L$ is context-free and $R$ is regular, then $L\cap R$ is context-free; they do not assert closure under intersection of two arbitrary context-free languages. The framework collects the common constructions without identifying the different language classes.^[ref]

Automata theory studies abstract machines, the formal languages they recognize and transformations between machine descriptions. The machine's permitted memory and transition rules determine its power. A finite-state automaton stores only one of finitely many states; a pushdown automaton additionally has a stack, while a Turing machine has unbounded working storage.

For example, a two-state finite-state automaton recognizes binary strings containing an even number of ones: reading1 switches state, reading0 preserves it, and the initial state is accepting. In contrast, recognizing all strings $a^n{b}^n$ requires remembering an unbounded count, which a finite-state automaton cannot do. A pushdown automaton can push once per $a$ and pop once per $b$. These comparisons separate language recognition from implementation details and motivate closure properties, minimization and decidability questions.

Choose a finite symmetric generating alphabet $\Sigma$ and one word $\sigma (g)$ representing each group element, with $\sigma (1)$ the empty word. The associated paths in the Cayley graph start at the identity and traverse one edge per unit time, remaining at their endpoint after completion. A synchronous combing has a constant $K$ such that paths to adjacent endpoints stay within $K$ at equal times. An asynchronous version permits increasing reparametrizations. The formal language need not be a regular language; regular synchronous representative languages define automatic groups.

For context-free grammars $G=(V,\Sigma ,P,S)$ and $G^{\prime }=(V^{\prime },\Sigma ,P^{\prime },S^{\prime })$ with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol $S_0$ and putThen $L(H)=L(G)L(G^{\prime })$, the concatenation of the two formal languages. After the first production, every production rule acts within one of the two component parse trees. Their terminal words form one word from $L(G)$ followed by one from $L(G^{\prime })$. Conversely, any pair of component derivations can be performed after $S_0\to S{S}^{\prime }$.

The construction does not work for arbitrary variable-based grammars. Let $G$ have production rules $S\to A$ and $Aa\to b$, and let $G^{\prime }$ have the single production rule $S^{\prime }\to a$. Here $L(G)$ is empty and $L(G^{\prime })=\{a\}$, but the combined formal grammar derives $S_0\Rightarrow S{S}^{\prime }\Rightarrow A{S}^{\prime }\Rightarrow Aa\Rightarrow b$. The production rule $Aa\to b$ consumes a terminal symbol supplied by the other component, crossing the boundary that context-free grammar rules preserve.

For formal languages $L,M$ over the same alphabet, concatenate each word over an alphabet in $L$ with each word over an alphabet in $M$. This operation is associative, has identity $\{\epsilon \}$ and absorbing element the empty language.

A context-free language is a formal language generated by a context-free grammar, in which each production has exactly one nonterminal on its left side. Equivalently, it is recognized by a nondeterministic pushdown automaton.

For example, the grammar $S\to 0S1\mid ϵ$ generates $\{0^n{1}^n:n\ge 0\}$. A derivation adds one matching pair at a time, while the empty production stops the process. The language is not regular: matching the two unbounded counts requires more memory than a finite-state recognizer provides. Context-free languages describe many nested structures, including balanced delimiters and recursive expression syntax.

Store the start nonterminal symbol on a stack. An epsilon transition nondeterministically replaces its top nonterminal symbol by a production rule right-hand side. A top terminal symbol can be removed only while consuming the same input symbol. With a protected stack bottom marker, enter a final control state when that marker is exposed. Requiring all input to have been read implements acceptance by final state. The stack records the unprocessed suffix of a leftmost derivation, proving equality of the recognized and generated formal languages.

The complexity class of complements of formal languages in P. A deterministic polynomial-time algorithm deciding a formal language can have its accepting and rejecting outcomes interchanged, so P is closed under complement and equals co-P.

A formal language whose complement of a set, relative to the set of all input words, is a recursively enumerable language. A recognizer for the complement detects every negative instance eventually and need not halt on positive instances. A formal language is a decidable language exactly when it and its complement are both recursively enumerable languages.

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 decision problem asks for one of two answers, conventionally encoded as zero and one. Equivalently, it asks whether an input belongs to a formal language.

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

The formal language containing no words over an alphabet. It differs from the language containing only the empty word, which is a multiplicative identity for concatenation of formal languages.

The complexity class of formal languages decidable in deterministic exponential time. It contains NP: enumerate the finitely many choices of a polynomial-length nondeterministic computation and simulate each branch with a polynomial time cutoff. There are at most $b^{p(n)}$ branches for fixed branching bound $b$ and polynomial $p$.

A finite-state automaton recognizes a nonempty formal language exactly when some accepting automaton state is reachable from an initial automaton state. Reachability in a graph decides this in a finite transition graph. For an Epsilon-NFA, include its epsilon transitions; the non-epsilon labels of a successful graph path give an accepted word.

A formal language with finitely many words. Every finite language is a regular language: take a finite union of the regular expressions spelling its members, with the empty language represented separately when there are no members.

Finite model theory studies first-order structures restricted to finite domains, and asks which properties can be expressed in specified formal languages. The restriction changes the available tools: ordinary first-order compactness does not hold when only finite models are admitted.

For example, the sentences saying there are at least $n$ distinct elements, one for every positive integer $n$, have a finite model for each finite subset but no common finite model. This is a direct failure of finite compactness. Logical games, locality, and bounded-variable fragments then compare the expressive power of formulas on finite databases and graphs, linking definability with computational complexity theory.

A finite-state machine processes inputs using a finite set of automaton states and input-dependent automaton transitions. An automaton state records everything the machine remembers; an automaton transition says how that memory changes on the next symbol. A finite-state machine may also emit outputs. Here the emphasis is on recognizing a formal language: start in a designated automaton state, read a word from an alphabet, and accept exactly when the final automaton state is designated accepting.

Finite memory does not impose a maximum input length. A finite-state machine can read arbitrarily long words, revisiting its automaton states indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For divisibility by three, a word of binary digits can describe an enormous integer, yet its congruence class modulo three is all that the machine needs to retain. Two already-read words giving the same automaton state behave identically under every subsequent continuation in a DFA.

This makes finite-state machines useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a regular expression. The beautiful design question is which distinctions about the past matter to the future. DFA minimization makes that question precise by merging indistinguishable states of a deterministic finite automaton. Both DFAs and NFAs recognize exactly the regular languages.

A formal grammar specifies how to generate a formal language by repeated applications of production rules. Write $G=(N,\Sigma ,P,S)$, where $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 production rules $\alpha \to \beta$. In an unrestricted formal grammar, the word $\alpha$ must contain at least one nonterminal symbol; $\beta$ may be any word over $N\cup \Sigma$.

A grammar derivation replaces an occurrence of $\alpha$ inside a word by $\beta$. The generated formal language isIntermediate words may still contain nonterminal symbols; these are sentential forms. For example, the production rules $S\to aSb$ and $S\to \epsilon$ give $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ and generate exactly $\{a^n{b}^n:n\ge 0\}$. Restricting each left side to one nonterminal symbol gives a context-free grammar.^[ref]

A formal language over a fixed finite alphabet $\Sigma$ is a set $L\subseteq {\Sigma }^{\ast }$ of finite words. Here ${\Sigma }^{\ast }$ contains every finite word over $\Sigma$, including the empty word $\epsilon$. A formal language may contain finitely or infinitely many such words.^[ref]

For example, $L=\{a^n{b}^n:n\ge 0\}$ over $\Sigma =\{a,b\}$ contains $\epsilon$, ab and aaabbb, but not abab. The notation specifies a set of permitted words; it does not itself give a running time for deciding membership. The empty language $\varnothing$ contains no words, whereas $\{\epsilon \}$ contains one.

Concatenation of formal languages combines permitted words from two formal languages. Automata theory and computability theory ask which machine models can recognize such sets, while computational complexity theory asks what resources membership decisions require.