Lemat Ogdena – uogólnienie lematu o pompowaniu dla języków bezkontekstowych. Służy do udowadniania, że dany język nie jest językiem bezkontekstowym.
Lemat mówi że:
Dla każdego języka bezkontekstowego istnieje taka stała że dla każdego słowa zawierającego co najmniej wyróżnionych pozycji, możemy podzielić na w taki sposób, że:
- słowo zawiera (przynajmniej jedną) wyróżnioną pozycję,
- słowo zawiera co najwyżej wyróżnionych pozycji,
- dla każdego mamy
Lemat o pompowaniu dla języków bezkontekstowych jest szczególnym przypadkiem, gdzie wszystkie litery słowa są wyróżnione.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.