Ogden's lemma

Ogden's Lemma, named after William Ogden , is a method of theoretical computer science that can be used to show that a formal language is not a context-free language , since it describes properties that must apply to all context-free languages. It thus only provides a necessary (not a sufficient) condition for classification as a context-free language. Ogden's lemma is therefore not suitable for proving freedom from context.

The pumping lemma is a special case of Ogden's lemma.

statement

Let be the class of all languages that can be generated by Chomsky hierarchy type 2 grammars, i.e. the class of context-free languages. ${\displaystyle {\mathcal {L}}_{2}}$

For there is a natural number such that for all words following applies: If in at least be marked letters, it can be as into five parts disassemble so that ${\displaystyle L\in {\mathcal {L}}_{2}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle z\in L}$ ${\displaystyle z}$ ${\displaystyle n}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle u,v,w,x,y}$

1. ${\displaystyle vx}$ contains at least one highlighted letter,
2. ${\displaystyle vwx}$contains the maximum number of marked letters, ${\displaystyle n}$
3. ${\displaystyle \forall i\geq 0:uv^{i}wx^{i}y\in L}$.

example

The language is not context-free. ${\displaystyle L=\{a^{i}b^{j}c^{k}d^{\ell }\ |\ i\neq 0\ \Rightarrow \ j=k=\ell \}}$

The proof that this language is not context-free cannot be provided with the pumping lemma for context-free languages, but with Ogden's lemma.

Proof by contradiction : We assume that itis context-free. Then, according to Ogden's lemma, there is a constant, so that for every wordand every marking thatmarksat leastcharacters in, there is a decomposition that fulfills the properties 1., 2. and 3.. ${\displaystyle L}$ ${\displaystyle n}$ ${\displaystyle z\in L}$ ${\displaystyle n}$ ${\displaystyle z}$

Let the constant be and especially for the word with a marking on the part there must be a decomposition that satisfies 1., 2. and 3.. ${\displaystyle n}$ ${\displaystyle z=ab^{n}c^{n}d^{n}\in L}$ ${\displaystyle b^{n}}$ ${\displaystyle z=uvwxy}$

Property 1. means that at least one contains. Property 2. is always fulfilled because there are only marked letters in . We consider all possible (not necessarily disjoint) cases of decomposition with at least one into and always find a contradiction to property 3. ${\displaystyle vx}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle z}$ ${\displaystyle b}$ ${\displaystyle vx}$

• ${\displaystyle vx\in \{a,b,c\}^{*}}$, then it follows that has more s than s (and at least one is at the beginning of the inflated word) ${\displaystyle uv^{2}wx^{2}y}$ ${\displaystyle b}$ ${\displaystyle d}$ ${\displaystyle a}$
• ${\displaystyle vx\in \{a,b,d\}^{*}}$, then contains more s than s (and at least one is at the beginning of the inflated word) ${\displaystyle uv^{2}wx^{2}y}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle a}$
• ${\displaystyle vx}$contains both s and s, then must appear in or in two kinds of letters. But then the structure of no longer corresponds to the form . ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle v}$ ${\displaystyle x}$ ${\displaystyle uv^{2}wx^{2}y}$ ${\displaystyle a^{*}b^{*}c^{*}d^{*}}$

So we always bring property 3. to the contradiction, since the word is not in . ${\displaystyle i=2}$ ${\displaystyle uv^{2}wx^{2}y}$ ${\displaystyle L}$

swell

• William Ogden: A helpful result for proving inherent ambiguity . In: Mathematical Systems Theory . 2, Springer Science & Business Media, Dordrecht 1968. ISSN  0025-5661 . Pp. 191-194.