למת הניפוח לשפות רגולריות
ויקיפדיה האנציקלופדיה encyclopedia
למת הניפוח נועדה להוכיח ששפה כלשהי איננה שפה רגולרית. הלמה מגדירה תנאי הכרחי לרגולריות שפה, והשימוש העיקרי בה הוא בהוכחה בדרך השלילה ששפה איננה רגולרית על ידי הוכחת אי קיומו של התנאי עליו מדברת הלמה. הלמה נוסחה והוכחה על ידי יהושע בר-הלל, מיכה פרלס, ואלי שמיר מהאוניברסיטה העברית בירושלים.[1]
ערך זה עוסק בלמת הניפוח לשפות רגולריות. אם התכוונתם ללמת הניפוח לשפות חופשיות הקשר, ראו למת הניפוח לשפות חופשיות הקשר.