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.

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

Every generated word satisfieswhere ${\#}_a,{\#}_b$ count occurrences of the indicated terminal symbols. To see this, follow the unique chain of $S$ occurrences in a parse tree. Each use of $S\to UST$ introduces one $a$ from $U$, at least one $b$ from its rightmost $T$, and possibly one further $b$ from $U\to aT$. Each use of $S\to ST$ adds one $b$ and no $a$. The terminating $S\to \epsilon$ contributes neither. Hence no generated word has more $a$ symbols than $b$ symbols.

Also, for every $n\ge 0$, the word $a^n{b}^n$ is generated: apply $S\to UST$ exactly $n$ times, choose $U\to a$ each time, then use $S\to \epsilon$ and all remaining $T\to b$.

Suppose $L(G)$ were a regular language, and let $p\ge 1$ be a pumping length from the pumping lemma for regular languages. Apply it to $w=a^p{b}^p$. Every allowed decomposition $w=xyz$ with $|xy|\le p$ and $|y|>0$ has $y=a^r$ for some $r\ge 1$. Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore $L(G)$ is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.

In strict Chomsky normal form, every production of a context-free grammar is $A\to BC$ or $A\to a$, with $A,B,C$ nonterminal symbols and $a$ a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language $\{\epsilon \}$, generated by $S\to \epsilon$, is therefore not generated by any strict CNF grammar.

The convention matters: extended Chomsky normal form permits $S\to \epsilon$ with $S$ excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

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 in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. Under this strict convention there is no epsilon production, so such a grammar cannot generate the empty word. Conversion of an arbitrary grammar therefore givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.

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.

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals and $a$ is a terminal symbol; one may additionally allow the new start production $S_0\to ϵ$ when the language contains the empty string, provided $S_0$ never appears on a right-hand side.

The standard conversion proceeds as follows.

The terminal alphabet $\Sigma$ may be kept unchanged throughout, although unused terminals may be discarded by convention. Every stage preserves the generated language, with the explicit protection of $ϵ$ at the start-symbol stage. For example,is already in Chomsky normal form and generates the infinite language $\{a^n:n\ge 1\}$, so its conversion may be the grammar itself.

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.

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.

In a formal grammar, terminal symbols are symbols of completed words; a nonterminal symbol is an auxiliary symbol that may be replaced by a production. The two alphabets are disjoint.