אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/למת הניפוח לשפות רגולריות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 51:
==הרחבה של הלמה ==
בלמה שראינו לעיל, אחת הדרישות היא <math>|uv|\le n</math>, ומשמעותה שה"לולאה" שנוצרת נמצאת קרוב לתחילת המילה <math>x</math>. דרישה זו היא מלאכותית – אם ניקח מילה <math>x</math> ארוכה
{{משפט
|שם=למת הניפוח ''המוכללת'' לשפות רגולריות
|תוכן=לכל שפה רגולרית <math>L</math> קיים מספר <math>n</math> כך
# <math>|v|>0</math>
# לכל <math>i\in \{0,1,2,\ldots\}</math> גם המילה <math>\alpha uv^iw\gamma</math> שייכת לשפה <math>L</math>}}
ניתן לחשוב על תת-המחרוזת <math>\beta</math> כעל המילה אותה ניפחנו בלמה ה"פשוטה" שהצגנו למעלה. החלוקה <math>x=\alpha\beta\gamma</math> מאפשרת לבחור את החלק לניפוח בכל מקום במילה, ולא רק
{{אוטומטים ושפות פורמליות|מוגבל}}
| |||