Ogden's lemma

Ogden's lemma is a method of theoretical computer science, with which it can be shown that a formal language is not context-free language, because it describes properties that must hold for all context-free languages. It thus provides only a necessary ( not sufficient) condition for classification as context-free language. Ogden's lemma is therefore not suitable to prove the context of freedom.

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

Assumptions

Be the class of all languages ​​that can be generated by Chomsky hierarchy type 2 grammars, ie the class of context- free languages ​​.

Statement

Be a context-free language,. Then there is a natural number such that the following applies to all words: If marked in letters at least, it can be decomposed as in five parts so that

Example

The language is not context-free.

Evidence that this language is not context-free, can not be performed with the pumping lemma for context-free languages, but with Ogden's Lemma.

Proof by contradiction: We assume that is context-free. Then there exists according to Ogden's lemma is a constant such that for every word and label marking at least characters in a decomposition exists, the 1st, 2nd and 3rd satisfies the properties.

The constant was then, and in particular for the word mark on the part, there must be a separation, the 1st, 2nd and 3rd fulfilled.

Feature 1 means that at least one contains. Property 2 is always satisfied, since there is only marked in letters. We consider all possible (not necessarily disjoint ) cases of decomposition with at least one in and always find a contradiction with property 3

  • , It follows that more than S S ( and at least one is at the beginning of the inflated word)
  • , Then s contains more than s ( and at least one is at the beginning of the inflated word)
  • Contains both s and s, then letters must occur in or in two varieties. But then no longer corresponds to the structure of the form.

So we lead to a contradiction with property 3 always, since the word is not in.

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.
  • Theory of formal languages
614536
de