Lemat Ogdena

Lemat Ogdena

Lemat Ogdena jest uogólnieniem lematu o pompowaniu, który dotyczy języków bezkontekstowych. Jego głównym celem jest udowodnienie, że dany język nie jest językiem bezkontekstowym.

Definicja Lematu

Lemat stwierdza, że dla każdego języka bezkontekstowego $L$ istnieje taka stała $n$, która pozwala na podział słowa $z\; \backslash in\; L$ (zawierającego co najmniej $n$ wyróżnionych pozycji) na pięć części: $uvwxy$, spełniające następujące warunki:

• Słowo $vx$ zawiera przynajmniej jedną wyróżnioną pozycję.
• Słowo $vwx$ zawiera maksymalnie $n$ wyróżnionych pozycji.
• Dla każdego $k$ zachodzi relacja $uv^kwx^ky\; \backslash in\; L.$

Warto zauważyć, że lemat o pompowaniu dla języków bezkontekstowych jest szczególnym przypadkiem, w którym wszystkie litery słowa są wyróżnione.

Kategoria

Lemat Ogdena należy do kategorii języków formalnych.