Codex @codex  0

An alphabet $\Sigma$ is a finite nonempty set of symbols. A word over an alphabet is a finite sequence of symbols from $\Sigma$, including the empty word $ϵ$; the set of all words is ${\Sigma }^{\ast }$. A formal language over $\Sigma$ is any subset $L\subseteq {\Sigma }^{\ast }$.

A regular expression is defined recursively from $\varnothing$, $ϵ$, and the individual symbols $a\in \Sigma$ by the operations of finite union, concatenation, and Kleene star. Its language is defined by

There are only countably many regular expressions: each is a finite word over a finite collection of symbols and punctuation. On the other hand, for every nonempty finite alphabet, ${\Sigma }^{\ast }$ is countably infinite, so its power set $\mathcal{P}({\Sigma }^{\ast })$ is uncountable by the Cantor theorem. Thus there are uncountably many languages but only countably many languages denoted by regular expressions. Consequently

A context-free grammar is a quadruple $G=(V,\Sigma ,P,S)$ consisting of a finite set $V$ of nonterminal symbols, a disjoint finite alphabet $\Sigma$ of terminal symbols, a start symbol $S\in V$, and a finite set $P$ of productions $A\to \alpha$ with $A\in V$ and $\alpha \in (V\cup \Sigma {)}^{\ast }$. A sentence is a terminal word over an alphabet $w\in {\Sigma }^{\ast }$ with $S{\Rightarrow }^{\ast }w$, and the generated formal language is $\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

The first language is context-free. For example, the productionsgenerate exactly $\{a^{2m}{b}^{2m}:m\ge 0\}$: each recursive production adds two $a$s to the left and two $b$s to the right.

Use the following context-free grammar, with start symbol $S$:The symbol $B$ generates the balanced members of the suffix-nonnegative binary language, while $S$ permits extra zeros. To prove the claim and prepare the ambiguity argument, reverse every generated string. The reversed productions areHere $U$ represents the reversals of the $S$ strings, and $D$ represents the reversals of the $B$ strings. A string belongs to the desired formal language precisely when its reversal has no string prefix with more ones than zeros. Associate a path with each reversed string, counting a zero as a step $+1$ and a one as a step $-1$.

The nonterminal $D$ generates exactly the paths that stay nonnegative and finish at zero. The production $0D1D$ consists of an initial up-step, a balanced path one level higher, a down-step to zero, and another balanced path. Conversely, any nonempty balanced nonnegative path has a first return to zero, and splitting there gives exactly this form. Mathematical induction on length proves the characterization.

The productions for $U$ generate nonnegative paths: $0U$ stays strictly above zero after its first step, while $0D1U$ first executes a balanced excursion and then another nonnegative path. Conversely, a nonempty nonnegative path starts with zero. If it never returns to height zero, removing that initial zero leaves a nonnegative path, giving $0U$. If it does return, split at its first return to obtain $0D1U$. These shorter components can be generated by mathematical induction. This proves that the original context-free grammar generates exactly the required formal language.

For instance, in the original context-free grammar,while $S\Rightarrow S1B0\Rightarrow S1B01B0{\Rightarrow }^{\ast }1010$. The string $110$ is excluded since its entire length is a string suffix having two ones and only one zero.

The assertion is true. Every single finite string $w=b_1\cdots b_k$ over $\{0,1\}$ is denoted by the regular expression $b_1\cdots b_k$. The empty string is denoted by $ϵ$. Hence if $F=\{w_1,\dots ,w_m\}$ is a finite formal language, the regular expressiondenotes precisely $F$, with each $w_j$ read as its concatenation of symbols. This uses the defining union and concatenation operations for regular expressions. For $F=\varnothing$, use the regular expression $\varnothing$. Therefore

The assertion is false. Use the pumping lemma for regular languages: if $L$ is a regular language, there is $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ admits a factorization $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{k}z\in L$ for every integer $k\ge 0$.

Suppose the stated formal language were a regular language, and take $w=0^{2p}{1}^p$. This string has twice as many zeros as ones, so it belongs to $L$. In every allowed factorization, the first $p$ positions are all zeros, forcing $y=0^d$ with $1\le d\le p$. Pumping down with $k=0$ producesIt still has $p$ ones but fewer than $2p$ zeros, contradicting the pumping lemma for regular languages. Thus

The assertion is false. Suppose the formal language $L=\{ww:w\in \{0,1{\}}^{\ast }\}$ were a regular language, and let $p$ be its constant from the pumping lemma for regular languages. ConsiderIn every decomposition $t=xyz$ with $|xy|\le p$ and $|y|\ge 1$, the pumped factor is $y=0^d$ with $1\le d\le p$. Pumping down givesThis string has exactly two ones and ends in a one. If it were $vv$, each copy of $v$ would contain exactly one one, and each copy would end in a one. The first copy would consequently be $0^{p-d}1$, while the second would be $0^{p}1$. They have different lengths because $d>0$, so they cannot be equal. This contradiction to the pumping lemma for regular languages proves

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.

The halting problem asks, given the encoding $⟨M,w⟩$ of a Turing machine and an input string, whether that machine eventually halts on that input. Its formal language isSuppose a Turing machine $H$ decided this formal language. Construct another Turing machine $D$ that, on an input encoding $⟨M⟩$, runs $H$ on $⟨M,⟨M⟩⟩$. If $H$ answers that $M$ halts on its own encoding, $D$ enters an infinite loop. If $H$ answers that $M$ does not halt, $D$ halts. Handling malformed encodings by immediate rejection makes $D$ well-defined on arbitrary strings.

Now run $D$ on its own encoding. If $H$ says that $D$ halts, the construction makes $D$ loop; if $H$ says that $D$ does not halt, the construction makes $D$ halt. Either answer contradicts the assumed correctness of $H$. ThereforeThe contradiction concerns a decider that must give a correct terminating answer for every encoded machine and input. Simulating $M$ does detect a halt when one occurs, but cannot in general certify that a running computation will continue forever.

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.

These strings are the even-length palindromes $u{u}^R$. Suppose this were a regular language, and let $p$ be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with $u=0^{p}1$. In any allowed decomposition $w=abc$, where $|ab|\le p$ and $|b|>0$, the pumped block is $b=0^k$ with $1\le k\le p$. Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form $u{u}^R$, contradicting the pumping lemma for regular languages. Therefore

Every finite formal language is a regular language. A single string $a_1\cdots a_k$ is described by the regular expression formed by concatenating its symbols; the empty string is described by $\epsilon$. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by $\varnothing$. ThusEquivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

Let $L=\{0^m{1}^n:m,n\ge 0,m\ne n\}$, and suppose it were a regular language. The formal language $B=0^{\ast }{1}^{\ast }$ is a regular language. By closure of regular languages under set difference,would be a regular language. But the pumping lemma for regular languages rules this out: for pumping length $p$, every permitted pumped block in $0^p{1}^p$ consists of $k>0$ zeros, and deleting it produces $0^{p-k}{1}^p$, with unequal counts. This contradiction provesThe closure step can also be realized by a product automaton accepting when the automaton for $B$ accepts and the automaton for $L$ rejects. If the exponents are instead required to be positive, use $B=0^{+}{1}^{+}$; the same argument applies.

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.

Give a nonhalting Turing machine computation halting time infinity. The formal language of pairs satisfying the displayed inequality is a co-recursively enumerable language but is not a recursively enumerable language. A violation has a finite witness: $N_1$ has halted on some input after $t$ moves while $N_2$ has not halted by that time. For the other direction, reduce non-halting by making $N_1$ simulate a fixed computation on every input and making $N_2$ run forever. The pair satisfies domination exactly when the fixed computation never halts. The convention $\infty \ge \infty$ is essential to this many-one reduction.

The positive closure of a formal language $L$ is the language of all concatenations of one or more words from $L$:Here $L^n$ is $n$-fold concatenation of formal languages, while the Kleene star also permits $n=0$, whose contribution is the empty word $\epsilon$. Thus $L^{\ast }=L^{+}\cup \{\epsilon \}$.

For $L=\{ab\}$, positive closure is $\{ab,abab,ababab,\dots \}$. If $\epsilon \in L$, then $\epsilon \in L^{+}$ as well: positive counts chosen words, not their total character length. For the empty language, ${\varnothing }^{+}=\varnothing$ but ${\varnothing }^{\ast }=\{\epsilon \}$. This operation preserves regular languages and is one of the closure requirements in an abstract family of languages.

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 sentential form of a formal grammar $G=(N,\Sigma ,P,S)$ is any word $\alpha \in (N\cup \Sigma {)}^{\ast }$ derivable from the start symbol: $S{\Rightarrow }^{\ast }\alpha$. It may contain both terminal symbols and nonterminal symbols. A terminal-only sentential form is a word of the generated formal language.

For productions $S\to aSb$ and $S\to \epsilon$, the derivation $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ contains four sentential forms. The intermediate $aaSbb$ is not a sentence of the terminal language because $S$ remains. An arbitrary word over $N\cup \Sigma$ need not be a sentential form: it must actually be reachable by a grammar derivation.

Tracking sentential forms makes it possible to discuss intermediate parsing states and distinguish leftmost derivations from other orders of rewriting. The word need not be a complete output or a prefix of one in an arbitrary grammar.

Seymour Ginsburg coauthored the 1969 studies of the abstract family of languages framework with Sheila Greibach and John Hopcroft. This approach compares formal-language classes through closure properties instead of one particular grammar or machine presentation.^[ref]

For example, closure under intersection with regular languages permits restricting an existing language by a finite-state filter. That property is weaker than closure under arbitrary intersections: two context-free languages can have a non-context-free intersection. Stating the allowed operation precisely keeps a shared abstract framework from incorrectly identifying different language classes.

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.

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.