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

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

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

יהיו $L_{1},L_{2}$ שפות ח"ה, ויהיו $G_{1}=(V_{1},\Sigma ,P_{1},S_{1}),G_{2}=(V_{2},\Sigma ,P_{2},S_{2})$ הדקדוקים ח"ה המתאימים.

השפה $L=L_{1}\cup L_{2}$ הינה חסרת הקשר, מכיוון שניתן ליצור את הדקדוק $G=(V,\Sigma ,P,S)$ כך ש

• $V=V_{1}\cup V_{2}$
• $P=P_{1}\cup P_{2}$
• $S=S_{1}\mid S_{2}$

כלומר המשתנה הראשון יכול להוביל אל $S_{1}$, אשר יוצר את כל המילים של $L_{1}$, או אל $S_{2}$, אשר יוצר את כל המילים של $L_{2}$.

סגירות לשרשור

יהיו $L_{1},L_{2}$ שפות ח"ה, ויהיו $G_{1}=(V_{1},\Sigma ,P_{1},S_{1}),G_{2}=(V_{2},\Sigma ,P_{2},S_{2})$ הדקדוקים ח"ה המתאימים.

השפה $L=L_{1}L_{2}$ הינה חסרת הקשר, מכיוון שניתן ליצור את הדקדוק $G=(V,\Sigma ,P,S)$ כך ש

• $V=V_{1}\cup V_{2}$
• $P=P_{1}\cup P_{2}$
• $S=S_{1}S_{2}$

המשתנה ההתחלתי מייצר מחרוזת שתחילתה במילה מ$L_{1}$ וסופה מילה מ-$L_{2}$, ולכן יוצר את כל השרשורים.

סגירות להפיכה לאחור

אם $L$ שפה ח"ה אזי גם $L^{R}$ חסרת הקשר. נבנה דקדוק $G^{R}$ מהדקדוק של $L$ בכך ש"נהפוך" כל כלל יצירה. פורמלית, לכל כלל יצירה $A\to \alpha$ ב-P (כך ש$A\in V,\alpha \in (\Sigma \cup V)^{*}$, נוסיף ב $G^{R}$ את כלל היצירה $A\to \alpha ^{R}$.

קל לראות שהדקדוק $G^{R}$ יוצר בדיוק את כל המילים ההפוכות מאלו מיוצרות על-ידי $G$.

חיתוך עם שפה רגולרית

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

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

באופן פורמלי, בהנתן אוטומט סופי $D=(Q_{D},\Sigma ,q_{0}^{D},F_{D},\delta _{d})$ עבור $L_{1}$ (רגולרית) ואוטומט מחסנית $P=(Q_{P},\Sigma ,\Gamma ,q_{0}^{P},F_{P},\delta _{P})$ עבור $L_{2}$ (ח"ה), נוכל לבנות אוטומט מחסנית חדש

$C=(Q,\Sigma ,\Gamma ,q_{0},F,\delta )$

כך שמתקיים:

• $Q=(Q_{D}\times Q_{P})$
• $q_{0}=(q_{0}^{D},q_{0}^{P})$
• $F\subseteq Q$ כך שכל מצב $(a,b)\in F$ מקיים $a\in F_{D},b\in F_{P}$
• פונקציית המעברים מתארת מעבר של כל אחת מהמכונות בנפרד, כך שרק המכונה P משתמשת במחסנית. לכל מעבר $\delta _{D}(a,x)\to b$ באוטומט D ומעבר $\delta _{P}(c,x,\sigma )\to (d,\gamma )$ באוטומט המחסנית P, נוסיף למכונה החדשה את המעבר $\delta ((a,c),x,\sigma )\to ((b,d),\gamma )$ נשים לב שבשתי המכונות הקלט הנקרא הינו זהה - x.

פעולות שאינן סגורות עבור שפות חסרות הקשר

חיתוך

קל לראות שהשפות $L_{1}=\{0^{n}1^{n}2^{m}\mid n,m\geq 0\},L_{2}=\{0^{m}1^{n}2^{n}\mid n,m\geq 0\}$ הינן חסרות הקשר, אבל השפה $L_{1}\cap L_{2}=\{0^{n}1^{n}2^{n}\mid n\geq 0\}$ אינה חסרת הקשר (זאת מוכיחים בעזרת למת הניפוח לשפות חסרות הקשר)

משלים

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

הפרש

אם $L_{1},L_{2}$ חסרות הקשר אזי $L=L_{1}\smallsetminus L_{2}$ הינה למעשה $L=L_{1}\cap {\overline {L_{2}}}$ ומכיוון שהפעולות לעיל אינן סגורות, גם פעולה זו אינה סגורה, כלומר, ייתכן ש-$L$ אינה ח"ה.

הפרק הקודם: תכונות של שפות חסרות הקשר

תכונות סגור

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