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

סגירות תחת איחוד עריכה

טענה: עריכה

אם   שפות רגולריות אזי גם   רגולרית

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

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

סגירות תחת שרשור עריכה

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

אם   שפות רגולריות אזי גם   רגולרית

הוכחה:
יהיו   אוטומטים סופיים (דטרמיניסטיים) שמכריעים את השפות לעיל. נבנה מכונה   שמכריעה את  .

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

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

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

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

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

 

הוכחה:
תהי   אס"ד עבור  , ונבנה מכונה עבור   באופן הבא: כל מצב מקבל במכונה   יחובר במעבר-אפסילון אל המצב ההתחלתי. על מנת לקבל את המילה  , נוסיף מצב מקבל לפני המצב ההתחלתי (או נחבר את המצב ההתחלתי, במעבר-אפסילון, למצב מקבל חדש).

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

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

 


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

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

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

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

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


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

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

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

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

תרגיל עריכה


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

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

 
 

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

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

 

נשים לב כי   מוגדרת מעל האלפבית   בעוד   מוגדרת מעל האלפבית  , שיכול להיות זהה ל , או שונה ממנו.

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

אם   שפה רגולרית, ו  הומומורפיזם, אזי גם   רגולרית

הוכחה:
יהי   אוטומטים סופיים (דטרמיניסטיים) שמכריע את השפה  . נבנה מכונה   שמכריעה את  . בגלל ההומומורפיזם, במקום כל אות   בשפה המקורית, תופיע המחרוזת   בשפה החדשה. לכן, אנחנו רוצים להחליף כל מעבר   ב-M ב"מעבר" מהצורה  , אבל זהו אינו מעבר תקין כי   עשויה להיות מחרוזת ארוכה, ומעבר מוגדר עבור תו יחיד. כדי לעקוף בעיה זו נחליף את המעבר במספר מעברים המתארים את המחרוזת  . למשל, אם הקשת המקורית (בין מצב q ל p) היתה עבור 0, והמיפוי הוא  , נוסיף מצב ביניים pq ונוסיף את המעברים   ו- . קל לראות שהמכונה החדשה הינה אסל"ד המקבל את  .

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

עבור הומומורפיזם   ניתן להגדיר את המיפוי ההופכי   כך שמתקיים

 

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

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

תרגיל עריכה

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

 

רגולרית.

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

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

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

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

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

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

נשים לב שכל הפעולות שביצענו סגורות עבור שפות רגולריות. לכן, אם L רגולרית גם   רגולרית; החיתוך   הינו חיתוך של שתי שפות רגולריות ולכן רגולרי גם הוא, וכן הפעלת ההומומורפיזם   על החיתוך הרגולרי, נותן שפה רגולרית. מכאן נובע שבהכרח   רגולרית.



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