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

סגירות תחת איחוד

טענה:

אם $L_{1},L_{2}$ שפות רגולריות אזי גם $L_{1}\cup L_{2}$ רגולרית

הוכחה:
יהיו $M_{1},M_{2}$ אוטומטים סופיים (דטרמיניסטיים) שמכריעים את השפות לעיל. נבנה מכונה $M$ שמכריעה את $L_{1}\cup L_{2}$ . אנחנו יכולים לבחור האם $M$ דטרמיניסטית או לא, מכיוון שהמודלים שקולים.

המכונה $M$ תתחיל במצב התחלתי חדש, שיחובר במעברי-אפסילון אל המצבים ההתחלתיים של $M_{1}$ או $M_{2}$ בהתאמה. בהנתן קלט ששיך ל $L_{1}\cup L_{2}$ המכונה "תנחש" לאיזה משתי המכונות לעבור, ותקבל את הקלט. מצד שני, אם הקלט אינו ב- $L_{1}\cup L_{2}$ , אזי לא משנה לאיזה מהמכונות נעבור בצעד הראשון, מסלול החישוב לא יסתיים במצב מקבל (כי הקלט אינו ב- $L_{1}$ ולא ב- $L_{2}$ ).

סגירות תחת שרשור

טענה: סגירות שפות רגולריות לשרשור

אם $L_{1},L_{2}$ שפות רגולריות אזי גם $L_{1}\circ L_{2}$ רגולרית

הוכחה:
יהיו $M_{1},M_{2}$ אוטומטים סופיים (דטרמיניסטיים) שמכריעים את השפות לעיל. נבנה מכונה $M$ שמכריעה את $L_{1}\circ L_{2}$ .

נחבר על-ידי מעבר אפסילון את המצבים המקבלים של $M_{1}$ עם המצב ההתחלתי של $M_{2}$ . אם הקלט הינו שרשור של מילה ב- $L_{1}$ עם מילה ב- $L_{2}$ , המכונה הראשונה תנתח את החלק הראשון ובדיוק בסיומו תעבור למכונה שניה, שתקבל את הקלט. המצבים המקבלים של $M_{1}$ הופכים להיות מצבים רגילים.

סגירות תחת כוכב

טענה: סגירות שפות רגולריות לפעולת הכוכב

אם $L$ שפה רגולרית אזי גם $L^{*}$ רגולרית

ניזכר בהגדרת הכוכב:

L^{*}=\{z\mid \exists n\geq 0{\text{ s.t. }}z=x_{1}x_{2}\ldots x_{n}{\text{ and }}\forall i,x_{i}\in L\}

הוכחה:
תהי $M_{1}$ אס"ד עבור $L$ , ונבנה מכונה עבור $L^{*}$ באופן הבא: כל מצב מקבל במכונה $M_{1}$ יחובר במעבר-אפסילון אל המצב ההתחלתי. על מנת לקבל את המילה $\epsilon$ , נוסיף מצב מקבל לפני המצב ההתחלתי (או נחבר את המצב ההתחלתי, במעבר-אפסילון, למצב מקבל חדש).

סגירות תחת היפוך לאחור (reverse)

נגדיר את פעולה ההיפוך לאחור על שפה, בתור כל המילים בשפה, רשומות מהסוף להתחלה:

L^{R}=\{z\mid \exists x\in L{\text{ s.t. if }}x=x_{1}x_{2}\ldots x_{n},z=x_{n}x_{n-1}\ldots x_{1}\}

האם פעולה זו סגורה עבור שפה רגולרית?

אם ניקח מכונה ופשוט "נהפוך" את כיווני החיצים, האם נקבל מכונה אשר מכריעה את

L^{R}

?

נשים לב שאחרי הפיכת הכיוונים, מתקבל אסל"ד ולא אס"ד.

טענה: שפה רגולרית סגורה תחת היפוך

אם $L$ שפה רגולרית אזי גם $L^{R}$ רגולרית

סגירות תחת השלמה

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

אם $L$ שפה רגולרית אזי גם ${\overline {L}}$ רגולרית

תכונה זו קלה ביותר להוכחה - נקח את האס"ד של $L$ ונהפוך כל מצב מקבל למצב לא מקבל, וכל מצב לא-מקבל למצב מקבל. מכונה זו מכריעה את ${\overline {L}}$ .

תרגיל

תרגיל :
הוכח כי שפות רגולריות סגורות תחת הפרש, כלומר בהנתן

L_{1},L_{2}

גם

L_{1}\smallsetminus L_{2}

רגולרית

לפי הזהות: $L_{1}\smallsetminus L_{2}=L_{1}\cap {\overline {L_{2}}}$

סגירות תחת הומומורפיזם

הומומורפיזם הוא פונקצית מיפוי בין שני אלפבתים $h:\Sigma \to \Delta$ (או באופן כללי מאלפבית $\Sigma$ למחרוזת כלשהי מעל האלפבית $\Delta ^{*}$ , כלומר מיפוי מהצורה $h:\Sigma \to \Delta ^{*}$ ), ומתקיים תמיד:

h(\varepsilon )=\varepsilon

h(xy)=h(x)h(y)

למשל, נניח כי $\Sigma =\{0,1\}$ ו- $\Delta =\{a,b,c\}$ ונגדיר את ההומומורפיזם $h(0)=a,h(1)=bc$ . מתכונות ההומורפיזם נובע כי מיפוי של מילה מסויימת הוא למעשה הפעלת המיפוי על כל אות בנפרד. לכן, למשל $h(0011)=aabcbc$

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

h(L)=\{h(w)\mid w\in L\}

נשים לב כי $L$ מוגדרת מעל האלפבית $\Sigma$ בעוד $h(L)$ מוגדרת מעל האלפבית $\Delta$ , שיכול להיות זהה ל $\Sigma$ , או שונה ממנו.

טענה: שפה רגולרית סגורה תחת הומומורפיזם

אם $L$ שפה רגולרית, ו $h:\Sigma \to \Delta ^{*}$ הומומורפיזם, אזי גם $h(L)$ רגולרית

הוכחה:
יהי $M$ אוטומטים סופיים (דטרמיניסטיים) שמכריע את השפה $L$ . נבנה מכונה $M_{h}$ שמכריעה את $h(L)$ . בגלל ההומומורפיזם, במקום כל אות $\alpha$ בשפה המקורית, תופיע המחרוזת $h(\alpha )$ בשפה החדשה. לכן, אנחנו רוצים להחליף כל מעבר $\delta (q,\alpha )=p$ ב-M ב"מעבר" מהצורה $\delta (q,h(\alpha ))=p$ , אבל זהו אינו מעבר תקין כי $h(\alpha )$ עשויה להיות מחרוזת ארוכה, ומעבר מוגדר עבור תו יחיד. כדי לעקוף בעיה זו נחליף את המעבר במספר מעברים המתארים את המחרוזת $h(\alpha )$ . למשל, אם הקשת המקורית (בין מצב q ל p) היתה עבור 0, והמיפוי הוא $h(0)=ab$ , נוסיף מצב ביניים pq ונוסיף את המעברים $\delta (q,a)=pq$ ו- $\delta (pq,b)=p$ . קל לראות שהמכונה החדשה הינה אסל"ד המקבל את $h(L)$ .

הומומורפיזם הופכי

עבור הומומורפיזם $h$ ניתן להגדיר את המיפוי ההופכי $h^{-1}:\Delta ^{*}\to \Sigma ^{*}$ כך שמתקיים

h^{-1}(L)=\{w\mid h(w)\in L\}

נשים לב ש $h^{-1}(L)$ מוגדרת מעל האלפבית $\Sigma$ ואילו $L$ במקרה זה מוגדרת מעל $\Delta$ . כלומר, קבוצת כל המילים, שאם נפעיל עליהם את ההומומורפיזם $h$ , נקבל מילה ב- $L$ . גם פעולה זו סגורה עבור שפות רגולריות.

הוכחה
בהינתן מכונה M שמכריעה את L נבנה את המכונה $M_{h}$ שמכריעה את ההמומורפיזם ההופכי. הרעיון, הוא שניתן "להפעיל" את $h$ על מילת הקלט ולקבל מילה ב- $L$ , אותה ניתן להכריע בעזרת המכונה M. עבור כל אות $\alpha$ בקלט, נדאג שהמכונה החדשה תעבור מהמצב הנוכחי למצב אליו $M$ היתה עוברת אם היתה מעבדת את הקלט $h(\alpha )$ . באופן פורמלי, לכל מצב $q\in Q_{M}$ , ולכל אות $\alpha \in \Sigma$ , אם המכונה M עוברת למצב p לאחר קריאת המחרוזת $h(\alpha )$ , אזי במכונה $M_{h}$ נוסיף את המעבר $\delta (q,\alpha )=p$ . קיבלנו אס"ד עבור $M_{h}$ .

תרגיל

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

{\text{No-End}}(L)=\{w_{1}w_{2}\ldots w_{n-1}\mid w_{1}w_{2}\ldots w_{n-1}w_{n}\in L\}

רגולרית.

פתרון

נניח כי L מוגדרת מעל האלפבית

\Sigma

ונגדיר אלפבית חדש

\Sigma '

, בו קיימות כל האותיות ב-

\Sigma

, אבל עם גרש. כמו כן נגדיר

\Delta =\Sigma \cup \Sigma '

. למשל, אם

\Sigma =\{0,1\}

אזי

\Delta =\{0,1\}\cup \{0',1'\}

.

ראשית נתחיל עם השפה L ובעזרת הומומורפיזם הופכי "ננפח" אותה לשפה בה מופיעות כל המילים ב-L, אבל מעל כל אות יכול להופיע גרש. כלומר, אם ב-L היתה המילה 10, אזי בשפה החדשה יהיו המילים $10,10',1'0,1'0'$ . ניתן לעשות זאת על-ידי ההומומורפיזם $h(0)=0,h(1)=1,\quad h(0')=0,h(1')=1$ . השפה הרצויה הינה בדיוק $h^{-1}(L)$ .

הרעיון כעת הוא "למחוק" את האותיות עם הגרש, למשל על-ידי הומומורפיזם מהצורה $g(0)=0,g(1)=1,\quad g(0')=\varepsilon ,g(1')=\varepsilon$ . אבל אנחנו לא יכולים לבצע את המחיקה ישירות על $h^{-1}(L)$ כי הגרש נמצא בכל מקום. מצד שני אם היינו יודעים שהגרש נמצא אך ורק על האות האחרונה, היינו יכולים למחוק אותה בעזרת g.

כעת נגדיר שפה $L_{mask}$ - שפה זו תשמש אותנו לבחור חלק מהמילים ב- $h^{-1}(L)$ . שפה זו תכיל את כל המילים בעולם בהן האות האחרונה בלבד מכילה גרש. קל לתאר את השפה בעזרת הביטוי הרגולרי $(0+1)^{*}(0'+1')$ ולכן ברור כי היא רגולרית.

כעת נבצע חיתוך בין שפת המיסוך לבין $h^{-1}(L)$ . כל המילים בהן קיים גרש באמצע המילה - לא יישרדו את החיתוך, ונקבל אך ורק מילים ב-L שמכילות גרש באות האחרונה. בדוגמא לעיל, לאחר החיתוך המילה היחידה שתשאר היא $10'$ (כי שאר שלוש המילים לא שייכות לשפה $L_{mask}$ באופן ברור).