פורטל:מדעי המחשב/הידעת?
קפיצה לניווט
קפיצה לחיפוש
למת הניפוח היא שמן של שתי טענות עזר במדעי המחשב.
למת הניפוח לשפות רגולריות מסייעת להראות ששפה פורמלית נתונה איננה שפה רגולרית. הטענה מציגה תנאי הכרחי לכך ששפה תהיה רגולרית; שפה שאינה מקיימת תנאי זה, איננה יכולה להיות רגולרית.
באופן דומה, למת הניפוח לשפות חופשיות הקשר מסייעת להראות ששפה פורמלית נתונה איננה שפה חופשית הקשר. בישראל היא נקראת גם למת בר הלל, על שם יהושע בר-הלל.