Ogdenin Lemma

Formaalisessa kieliteoriassa Ogdenin lemma tarjoaa laajennuksen hajautuslemman joustavuudelle yhteydettömille kielille .

Ogden Lemma sanoo, että jos kieli L on yhteydetön, on olemassa jokin luku p > 0 (missä p voi olla tai ei ole pumpun pituus), niin että mille tahansa merkkijonolle w , jonka pituus on vähintään p L: stä ja mille tahansa "merkintä" p tai useampia paikkoja w :ssä , w voidaan esittää muodossa

missä u , v , x , y ja z  ovat sellaisia ​​merkkijonoja, että

1. x sisältää vähintään yhden nimetyn sijainnin,
2. joko u ja v sisältävät merkityn paikan tai molemmat y ja z sisältävät sen ,
3. vxy sisältää enintään p merkittyjä paikkoja ja
4. uv i xy i z kuuluu L :lle mille tahansa i ≥ 0:lle.

Ogdenin Lemmaa voidaan käyttää osoittamaan, että tietty kieli ei ole yhteydetön, jos yhteydettömien kielten kasvulemma ei riitä. Esimerkki olisi kieli { a i b j c k d l  : i = 0 tai j = k = l }. Se on hyödyllinen myös joidenkin kielten olennaisen monitulkintaisuuden osoittamisessa.

Huomaa, että jos kaikki paikat on valittu, tämä lemma vastaa yhteydettömien kielten pumppauslemmaa.

Katso myös

• Kasvulemma kontekstittomille kielille
• Kasvu Lemma