אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/למת הניפוח לשפות רגולריות

עד כאן עסקנו בשפות רגולריות וראינו תכונות שלהן. כעת נשאל מהן שפות לא-רגולריות. כמובן שיש המון שפות כאלו, ולא נוכל לאפיין את כולן בצורה אחת, אבל יש באפשרותנו ליצור כלים הבוחנים האם שפה מסויימת היא רגולרית או לא. הכלי העיקרי נקרא למת הניפוח.

שפה לא רגולרית

נתחיל בדוגמא. האם ניתן לבנות אוטומט סופי לשפה הבאה:

$L=\{x\mid \#0's=\#1's\}$

נסו לבנות מכונה כזו, ונסו להבין מדוע הבנייה נכשלת.

ניכר כי למכונה הנ"ל צריכים להיות אינסוף מצבים, אשר "זוכרים" בכל רגע נתון, מה ההפרש בין כמות האפסים וכמות האחדים שהמכונה ראתה עד כה. נוכיח שאין מכונה כזו.

הוכחה: נניח בשלילה שקיים אס"ד שמכריע את השפה הנ"ל. נניח שלאוטומט יש n מצבים, ונביט על פעולתו עבור הקלט $0^{n+1}1^{n+1}$ אנחנו יודעים שבמהלך קריאת האפסים, האוטומט מגיע פעמים לאותו מצב (עקב עקרון שובך היונים), נסמן מצב זה ב -r. מכיוון שכל ה"זיכרון" של האוטומט הוא המצב, אנחנו יכולים "למחוק" את כל האפסים שבין שתי הפעמים שהאוטומט מגיע למצב r. נניח שבין שתי הפעמים נקראו i אפסים. אם כך הקלט $0^{n+1-i}1^{n+1}$ חייב להתקבל על-ידי המכונה, מכיוון שהיא עוברת בדיוק באותם מצבים כמו עבור הקלט $0^{n+1}1^{n+1}$, רק במקום להגיע פעמיים למצב r, היא מגיעה אליו פעם אחת (ואז ממשיכה כמו בקלט המקורי עד קבלת הקלט)

למת הניפוח

למת הניפוח לשפה רגולרית משתמשת ומכלילה את הרעיון שהוצג בדוגמא לעיל: העובדה שלאוטומט מספר מצבים סופי גורם לכך שהקלטים שהאוטומט מקבל חייבים להיות במבנה מסויים. ספציפית, אם האוטומט מקבל מילה כלשהי ארוכה דיה (ארוכה יותר ממספר המצבים של האוטומט), אז הוא חייב לקבל גם מילים שבנויות בצורה דומה למילה שהתקבלה ללא ה"חזרות" (ללא הקלט בין שתי הפעמים בהם האוטומט ביקר במצב r, בדוגמא לעיל.) באופן דומה, האוטומט חייב לקבל גם מילים שבנויות בצורה דומה אבל בתוספת החזרות. באופן מדוייק,

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

לכל שפה רגולרית $L$ קיים מספר $n$ כך שעבור כל מילה בשפה $x\in L$ הארוכה מ-$n$, ניתן לפרק את המילה $x$ לשלושה חלקים כך ש-$x=uvw$, ומתקיים

1. $|v|>0$
2. $|uv|\leq n$
3. לכל $i\in \{0,1,2,\ldots \}$ גם המילה $uv^{i}w$ שייכת לשפה $L$

הוכחה:

נניח ש-$L$ רגולרית, אזי קיים אוטומט $M$ שמכריע אותה, ויהי $n$ מספר המצבים ב-$M$. יהי $x\in L,|x|\geq n$. נביט על פעולת המכונה כאשר הקלט הוא $x$.

מכיוון שהאורך של הקלט הוא לכל הפחות $n$, המכונה מבצעת לפחות $n$ מעברים. נובע שהמכונה "מבקרת" בלכל הפחות n+1 מצבים (נסמנם $r_{0},r_{1},\ldots ,r_{|x|}$). לפי עקרון שובך היונים, לפחות שנים מהמצבים הנ"ל שווים, בהנ"כ נניח ש $r_{i}=r_{j},i<j$.

נשים לב שבין שני המצבים המכונה קוראת את הקלט $x_{i+1},x_{i+2},\ldots ,x_{j}$. נסמן מחרוזת זו ב-$v$. כלומר נוכל לפרק את x בצורה הבאה $x=u(v)w=x_{1}\cdots x_{i}(x_{i+1}\cdots x_{j})x_{j+1}\cdots x_{|x|}$ ולכן, לפי העקרון שראינו לעיל (המכונה לא יכולה להבדיל בין מצב $r_{i}$ למצב $r_{j}$), גם הוספת $v$ מספר פעמים, או השמטתו, לא משנות את העובדה שהמכונה מקבלת את הקלט, כלומר $uv^{i}w\in L$ לכל $i=0,1,2,\ldots$.

דוגמאות

שפה שאינה ניתנת לניפוח

השפה $\ L=\left\{a^{i}b^{i}|i\in \mathbb {N} \right\}$ ידועה כשפה לא רגולרית. נראה כיצד ניתן להשתמש בלמת הניפוח כדי להוכיח זאת.

נניח בשלילה כי השפה כן רגולרית, ונניח ש- $\ n$ הוא המספר שקיומו מובטח על ידי למת הניפוח. נביט במילה $\ a^{n}b^{n}$. אורכה גדול מ-$\ n$ (אורכה הוא בדיוק $\ 2n$) ולכן המילה ניתנת לניפוח, כלומר קיים לה פירוק $\ uvw$ כמתואר.

כעת, מכיוון ש-$\ |uv|\leq n$ בהכרח $\ uv=a^{k}$, כאשר $\ k\leq n$. זאת מכיוון ש-$\ n$ האותיות הראשונות במילה הן $\ a$.

לכן, $\ v=a^{t}$ כאשר $\ 1\leq t\leq k$. כעת נביט על המילה $\ uv^{0}w$, כלומר $\ uw$. מילה זו שייכת לשפה על פי למת הניפוח. אבל היא בדיוק מהצורה $\ a^{n-t}b^{n}$ ומכיוון ש-$\ t\geq 1$ הרי שבהכרח $\ n-t\neq n$, והגענו לסתירה, מפני שבכל המילים בשפה L מספר ה-$\ a$ וה-$\ b$ זהה. לכן $\ L$ אינה שפה רגולרית.

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

נביט בשפה $\ L=\left\{ab\right\}$, כלומר השפה שמכילה מילה בודדת: $\ ab$. ברור כי לא ניתן לנפח את השפה הזו - מכיוון שקיימת בה רק מילה אחת, אם נגדיל או נקטין את מספר האותיות בה נקבל מילה אחרת, שאינה שייכת לשפה. עם זאת, השפה רגולרית, כי כל שפה סופית היא רגולרית.

אין כאן סתירה עם למת הניפוח, מכיוון שבמקרה זה הלמה מתקיימת באופן ריק. נוכל לבחור $\ n=3$ ואז לא תהיה קיימת בשפה אף מילה שאורכה גדול מ-$\ n$. מכיוון שרק מילים מגודל זה ואילך אמורות להיות ניתנות לניפוח, הלמה כלל לא עומדת למבחן ולכן תנאיה מתקיימים.

בצורה דומה, כל שפה סופית מקיימת את תנאי למת הניפוח באופן ריק. פשוט בוחרים $\ n$ שגדול מגודלה של המילה הגדולה ביותר בשפה. בשפות אינסופיות זה בלתי אפשרי, כי בכל שפה אינסופית גודל המילים אינו חסום.

תרגיל

תרגיל : הוכח כי השפה $L=\{x\in 1^{*}\mid x=1^{p}{\text{ and }}p{\text{ prime}}\}$, אינה רגולרית
רמז: השתמש בלמת הניפוח, והראה שהשפה חייבת להכיל מחרוזת שאורכה מספר פריק, אם מנפחים מספיק

הרחבה של הלמה

בלמה שראינו לעיל, אחת הדרישות היא $|uv|\leq n$, ומשמעותה שה"לולאה" שנוצרת נמצאת קרוב לתחילת המילה $x$. דרישה זו היא מלאכותית – אם ניקח מילה $x$ ארוכה דיה, אין סיבה שנגביל את הניפוח ל-$\ n$ האותיות הראשונות. למעשה – כל תת-מחרוזת ארוכה דיה ב-$x$ תגרום לאוטומט הסופי לבקר במצב כלשהו פעמיים ותאפשר "ניפוח". רעיון זה מוביל ללמת הניפוח המוכללת המובאת להלן:

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

לכל שפה רגולרית $L$ קיים מספר $n$ כך שעבור כל מילה בשפה $x\in L$ הארוכה מ-$n$, ניתן לפרק את המילה $x$ לשלושה חלקים כך ש-$x=\alpha \beta \gamma$, ולכל פירוק כנ"ל המקיים $|\beta |\geq n$ ניתן לפרק את תת המחרוזת $\beta$ לשלושה חלקים $\beta =uvw$ ומתקיים

1. $|v|>0$
2. לכל $i\in \{0,1,2,\ldots \}$ גם המילה $\alpha uv^{i}w\gamma$ שייכת לשפה $L$

ניתן לחשוב על תת-המחרוזת $\beta$ כעל המילה אותה ניפחנו בלמה ה"פשוטה" שהצגנו למעלה. החלוקה $x=\alpha \beta \gamma$ מאפשרת לבחור את החלק לניפוח בכל מקום במילה, ולא רק בראשה.

הפרק הקודם: סגירות תחת פעולות שונות

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

הפרק הבא: משפט מיהיל-נרוד