#computational_models

שפה חסרת הקשר

שפה חופשית הקשר (או שפה חסרת הקשר) היא שפה פורמלית אשר קיים דקדוק חסר הקשר המגדיר אותה. כלומר, שפה $L$ היא שפה חופשית הקשר אם קיים דקדוק חסר הקשר $G$ כך ש $L$ היא אוסף כל המילים שניתן לגזור מהסימן התחילי של $G$ . ניתן להוכיח, ששפה היא חופשית הקשר אמ״מ קיים אוטומט מחסנית לא דטרמיניסטי המקבל אותה.

דקדוק חסר הקשר

זהו רביעייה $G = (V, Σ, R, S)$ המושגים החדשים שנכנסו לחיינו הם

$V = variables$ הנעלמים לשם הנוחות נעלמים נסמן באותיות גדולות ובאותיות קטנות נסמן טרמינלים שהם שילוב של נעלם עם אות מהשפה (איחוד של נעלם עם סיגמה ועל כל זה מפעילים סגור קליין).
$R$ אוסף כללי היצירה מהצורה ${g_{i} \to h_{i}}_{i = 1}^{| R |}$ כאשר $g_{i} \in V$ ו $h_{i} \in (V \cup Σ)^{*}$
דוגמה לכללי יצירה :
$S$ נעלם התחלתי.

גזירות

עבור דקדוק חסר הקשר אם יש כלל יצירה מהצורה $A \to z$ אז נסמן
$u A v \underset{G}{\Rightarrow} u z v$ . כאשר $u, v$ הם טרמינלים.

עבור שתי טרמנילים (תווים ב $Σ$ נקראים טרמינלים בהקשר של דקדוקים חסרי הקשר) $u, v$ נסמן $u \overset{*}{\underset{G}{\Rightarrow}} v$ אם ניתן לעבור מ $u$ ל $v$ על ידי 0 או יותר גזירות.

שפה של דקדוק

L(G)=\{w\in\Sigma^{*}\ |\ \ S\overset{*}{\underset{G}{\Rightarrow}}w  \}$$ כלומר, שיש סדרת גזירות שתעביר אותנו מהמצב ההתחלתי $S$ אל המחרוזת.  #### עצי גזירה טכניקה לגזירה של מילים באמצעות כללי גזירה היא עץ גזירה. בונים אותו באמצעות כללי הגזירה עד להגעת המילה הרצויה שמורכבת מתווים שכולם עלים. למשל עבור הדקדוק   $$\displaylines{ S\to AB \\ A\to a|AA|Ab \\ B\to bB|b }

נוכל לבנות עץ גזירה שהשורש שלו הוא $S$ וכל רמה $i$ בעץ תיגזר על ידי הרמה ה $i - 1$ למשל:

graph TD;
id1((S)) --> id2((A));
id1((S)) --> id3((B));
id7((B)) --> id8((b));
id2((A)) --> id4((A));
id2((A)) --> id5((A));
id4((A)) --> id9((a));
id5((A)) --> id10((a));
id3((B)) --> id6((b));
id3((B)) --> id7((B));

נקבל סך הכל :

S \to A B \to A b B \to A b b \to A A b b \to A a b b \to a a b b

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

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

תהי $L$ שפת חסרת הקשר. אזי, קיים $N$ כך שלכל $w \in L$ המקיים $ֿ # w \geq n$ אזי:
קיים פירוק $w = t u x y z$ כך ש

$| u y | > 0$
$| u x y | \leq n$
$\forall_{i \in N} : t u^{i} x y^{i} z \in L$

סגירויות

השפות חסרות הקשר סגורות ל

איחוד
שרשור
סגור קלין
reverse
prefix

והן אינן סגורות ל

חיתוך
משלים