למת הניפוח לשפות רגולריות

למת הניפוח היא דרך לבדוק אם שפה מתנהגת כמו מחשב קטן. היא הוצעה על ידי בר-הלל, פרלס ושמיר. אם מכונה קטנה יכולה לזהות שפה, אז במילים ארוכות יש קטע שחוזר. אפשר להוציא את הקטע הזה או לחזור עליו, והמילה תישאר בשפה. אם השפה רגולרית, יש מספר n כזה: כל מילה ארוכה מ-n מתחלקת ל-u, v, w כך ש- 1. החלק u ו-v...