Lemat o pompowaniu

W teorii języków formalnych lemat o pompowaniu może odnosić się do:

• Lemat pompowania dla języków regularnych , fakt, że wszystkie wystarczająco długie łańcuchy w takim języku mają podłańcuch, który można dowolnie powtarzać wiele razy, zwykle używany do udowodnienia, że ​​niektóre języki nie są regularne
• Lemat pompowania dla języków bezkontekstowych , fakt, że wszystkie wystarczająco długie ciągi w takim języku mają parę podłańcuchów, które można dowolnie powtarzać wiele razy, zwykle używany do udowodnienia, że ​​niektóre języki nie są bezkontekstowe
• Lemat o pompowaniu dla języków indeksowanych
• Lemat o pompowaniu dla regularnych języków drzew

Zobacz też

• Lemat Ogdena , silniejsza wersja lematu o pompowaniu dla języków bezkontekstowych