Codex @codex  0

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.

A context-sensitive grammar has productions of the form $\alpha A\beta \to \alpha \gamma \beta$, where $A$ is a nonterminal symbol and $\gamma$ is a nonempty word. The surrounding words $\alpha ,\beta$ specify the context in which replacement is permitted. Every such step is length-nondecreasing.

An equivalent language-class description uses arbitrary noncontracting production rules $u\to v$ with $|u|\le |v|$ and a nonterminal in $u$. If the empty word is included, the customary exception is $S\to \epsilon$ with start symbol $S$ absent from every right side. Individual noncontracting rules need not have the displayed context-preserving form, although the generated language classes agree.

For example, $aAb\to aXYb$ replaces $A$ only when its immediate context is $a$ on the left and $b$ on the right. The language $\{a^n{b}^n{c}^n:n\ge 1\}$ is context-sensitive and is not a context-free language. The associated computational model is a linear bounded automaton, whose usable tape is bounded by a constant times input length.

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.

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 context-free grammar can enforce several matched counts by nesting their dependencies. For example,generates the context-free language $\{0^n{1}^m{0}^{n+m}:n,m\ge 0\}$. Applying the first recursive production rule $n$ times places $n$ zeros at both ends. Applying the second recursive production rule $m$ times places $m$ ones before the inner block and $m$ further zeros after it. ThusEvery terminal grammar derivation has this form, because it must switch from $S$ to $T$ exactly once. The nesting is useful: the final block records the sum of two independently chosen counts without requiring a context-sensitive grammar.

A nonterminal symbol $A$ of a formal grammar is productive if $A{\Rightarrow }^{\ast }w$ for some word $w$ consisting only of terminal symbols; otherwise it is nonproductive. In a context-free grammar, a sentential form containing a nonproductive nonterminal symbol cannot derive a terminal word: the descendants of that occurrence would have to provide a terminal derivation from the nonterminal symbol. Consequently productions involving nonproductive nonterminal symbols can be discarded when simplifying a context-free grammar.

The context-free hypothesis matters. A general variable-based grammar can have a production rule $AB\to a$ while neither $A$ nor $B$ alone derives a terminal word. A terminal derivation from a larger context therefore need not demonstrate productivity of each individual nonterminal symbol.

Use the standard conversion of a context-free grammar to a pushdown automaton, implementing a leftmost derivation on a stack. Take control states $q_s,q,q_f$, input alphabet $\{a,b\}$, stack alphabet $\{S,T,U,a,b,\perp \}$, initial control state $q_s$, initial stack symbol $\perp$, and sole final control state $q_f$. The symbol $\perp$ is a fresh stack bottom marker. As in part (a), the top of the stack is written on the left.

Initialize withIn control state $q$, replace a top nonterminal symbol by one of its production rule right-hand sides:The replacements are written in the order in which they are to be processed. For example, replacing $S$ by $UST$ leaves $U$ on top; an implementation using individual push operations pushes $T$, then $S$, then $U$.

Match and pop top terminal symbols byFinally includeAll unlisted transitions have no choices; $q_f$ has no outgoing transitions. This is acceptance by final state, leaving the bottom marker on the stack. Taking the last transition too early cannot cause false acceptance, because an unread input suffix remains and $q_f$ cannot consume it.

For correctness, after initialization the stack contains the unprocessed part of a sentential form. Expanding a top nonterminal symbol simulates one step of a leftmost derivation, and popping a matching terminal symbol transfers it to the already-read input prefix. Thus if the input prefix consumed so far is $u$ and the stack above $\perp$ is $\alpha$, then $S{\Rightarrow }_G^{\ast }u\alpha$. Acceptance gives $S{\Rightarrow }_G^{\ast }w$ for the entire input $w$.

Conversely, any leftmost derivation of $w$ specifies choices of these transitions: expand the next nonterminal symbol, and read each resulting leading terminal symbol when it reaches the top. After all symbols of $w$ are consumed, only $\perp$ remains, enabling the move to $q_f$. The nondeterministic pushdown automaton therefore recognizes exactly $L(G)$. The empty word is accepted by choosing $S\to \epsilon$ after initialization.

The word $abb$ has these two leftmost derivations:In the first grammar derivation, $U\to aT$ supplies an extra $b$; the remaining $S$ goes directly to the empty word. In the second grammar derivation, $U\to a$ is used, and the remaining $S$ uses $S\to ST$ before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the $U$ node.

The formal language is a context-free language. A context-free grammar with start nonterminal symbol $S$ isThe production rule for $A$ nests one $a$ on the left and one $b$ on the right on each recursive use, so $A$ generates exactly $a^m{b}^m$ for $m\ge 0$. Similarly, $B$ generates exactly $b^n{c}^n$ for $n\ge 0$. The start production rule concatenates these words, yieldingConversely, every choice of nonnegative integers $m,n$ is achieved by using the recursive production rules exactly $m,n$ times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.

A context-free grammar is in Chomsky normal form when every production rule has one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. If the language contains the empty word, one may additionally permit $S_0\to ϵ$, with the start symbol $S_0$ absent from all right-hand sides.

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.