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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה אל: ניווט, חיפוש

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

טענה:[עריכה]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

תרגיל[עריכה]


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

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

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

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

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

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

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

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

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

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

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

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

תרגיל[עריכה]



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