אוטומטים ושפות פורמליות/ביטויים רגולריים

מהם ביטויים רגולריים?

נגדיר קבוצה זו בצורה אינדוקטיבית:

(בסיס 1) אות (מהאלפבית): $R=0$ לדוגמא
(בסיס 2) אות ריקה: $R=\varepsilon$
(בסיס 3) ביטוי ריק: $R=\emptyset$
(צעד 1) איחוד של ביטויים רגולריים: $R=(R_{1}\mid R_{2})$ (לעיתים מסומן על-ידי חיבור: $R=(R_{1}+R_{2})$ )
(צעד 2) שרשור: $R=R_{1}R_{2}$
(צעד 3) כוכב: $R=(R_{1})^{*}$

לדוגמא: $R=0^{*}(1^{*}0|0^{*}1)$ מתאים למילים שמתחילות ברצף אפסים, ואחריהן 1, או רצף אפסים ואז רצף אחדים ו-0. כל ביטוי שכנ"ל מתאים לשפה ספציפית. נסמן ב- $L(R)$ את השפה המתאימה לביטוי $R$ . בסיס האינדוקיציה מוגדר לפי:

$L(R=\emptyset )=\emptyset$
$L(R=\varepsilon )=\{\varepsilon \}$
$L(R=a)=\{a\}$

ושלוש הפעולת מגדירות:

$L(R_{1}+R_{2})=L(R_{1})\cup L_{(}R_{2})$
$L(R_{1}R_{2})=L(R_{1})L_{(}R_{2})$
$L(R^{*})=L(R)^{*}$

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

באופן אינטואיטבי - נוכל להבין ששלוש הפעולות לעיל מספיקות לפי הרעיונות הבאים:

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

כעת נוכיח את האינטואיציה לעיל באופן פורמלי.

שקילות ביטוי רגולרי לאוטומט סופי

כל ביטוי רגולרי מתאר שפה רגולרית

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

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

בסיס 1
בסיס 2
בסיס 3
צעד 1
צעד 2
צעד 3

לכל שפה רגולרית קיים ביטוי רגולרי המתאר אותה

הכיוון השני, יותר קשה, ונוכיח אותו כעת.

טענה:

אם $L$ רגולרית, אזי קיים ביטוי רגולרי $R$ כך ש $L=\{x\mid R{\text{ matches }}x\}$

הוכחה:
קיים לשפה אס"ד שנסמנו $M$ .

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

נביט על אמל"ד כלשהו. כל מצב נראה מהצורה הבאה:

מכיל כמה קשתות נכנסות
מכיל לולאה מעצמו לעצמו
מכיל כמה קשתות יוצאות

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

המקרה הכללי של מצב q והמרתו בביטוי רגולרי תואם

נניח ש $s_{1}$ הוא מצב ממנו ניתן לעבור למצב q, והמצב $t_{1}$ הוא מצב שניתן לעבור מ-q אליו. על-מנת לבטל את המצב-q, בלי לשנות את פעולת המכונה, צריך להוסיף קשת מs ל t, כך שאם במכונה המקורית היתה קשת $(s_{1},q)=R_{1}$ וקשת $(q,t_{1})=P_{1}$ ול-q קשת עצמית עם הביטוי הרגולרי $Q$ , נוסיף במכונה החדשה את הקשת $(s_{1},t_{1})=R_{1}Q^{*}P_{1}$ . נחזור על פעולה זו עבור כל זוג מצבים שניתן להגיע מהאחד לשני דרך, q, ונמחק את q. באופן כללי, ייתכן כי $s_{1}=t_{1}$ , ובמקרה זה הקשת החדשה תהיה לולאה עצמית במצב $s_{1}$ .

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

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

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

ביטויים רגולריים

הפרק הבא:
אוטומט מחסנית