דקדוק חופשי-הקשר

בשפות פורמליות, דקדוק חופשי-הקשר (גם: דקדוק חסר הקשר) הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה $\ A\to \alpha$ כאשר $\ A$ הוא משתנה דקדוקי ואילו $\ \alpha$ היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דקדוק חסר הקשר יוצר שפה חופשית הקשר (טיפוס 2 בהיררכיה של חומסקי).

המונח "חסר הקשר" מציין כי כלל היצירה עבור $\ A$ יכול להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של $\ A$, כלומר ללא חשיבות להקשר בו הוא מופיע. בדקדוק תלוי הקשר, לעומת זאת, ייתכנו כללי יצירה מהצורה $\ \alpha A\beta \to \alpha \gamma \beta$, כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A} הוא משתנה דקדוקי והפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \alpha,\beta,\gamma} הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים (ייתכן וריקות).

הגדרה

דקדוק חסר הקשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} מוגדר על ידי הרביעייה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V,\Sigma, R, S)} , כאשר:

1. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} - קבוצת משתנים
2. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
3. $R$ - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתניםהפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A\to\alpha)\in R \qquad A\in V, \alpha\in (V\cup \Sigma)^*}
4. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} - סימן ההתחלה. משתנה מתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} .

אומרים שהדקדוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} יוצר מילה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , אם ניתן להתחיל מהמשתנה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , ועל ידי ביצוע אחד או יותר מכללי היצירה שב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} , להגיע אל המילה $x\in \Sigma ^{*}$. מסמנים במקרה זה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\Rightarrow^* x} .

השפה הנוצרת על ידי הדקדוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} , היא אוסף כל המחרוזות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , אותן ניתן לייצר מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(G) = \{ x \mid S\Rightarrow^* x\}}

צורה נורמלית

ערך מורחב – הצורה הנורמלית של חומסקי

כל דקדוק חסר הקשר לא ריק שאינו יוצר את המילה הריקה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} , ניתן להמרה לדקדוק בו כל כלל יצירה הוא מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\to BC} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\to a} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B,C} משתנים ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} טרמינל. צורה זו נקראת הצורה הנורמלית של חומסקי על-שם הבלשן נועם חומסקי.

צורה אחרת לדקדוקים חסרי הקשר היא הצורה הנורמלית של גרייבך, הקרויה על-שם מדענית המחשב שילה גרייבך. בדקדוק זה כל כלל יצירה הוא מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\to a X} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} הוא טרמינל, ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} הוא רצף של אפס או יותר משתנים. לצורה זו כמה תכונות מעניינות, שכן כל כלל יצירה מוסיף בדיוק אות אחת למילה נוצרת, ולכן אורך המילה נתון על ידי כמות כללי היצירה שהופעלו. כמו כן, ניתן להמיר כל דקדוק מצורת גרייבך לאוטומט מחסנית שאין בו מעברי-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} , ובכך להראות כי תמיד ניתן לבטל מעברי-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon} באוטומטי מחסנית.

דו-משמעות

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

ראו גם

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

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000 (הספר במיזם פא"ר)

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison-Wesley, 2006. מסת"ב 0-321-45536-3.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. מסת"ב 0-201-02988-X.

קישורים חיצוניים

• גדי אלכסנדרוביץ', מבוא לדקדוקים חסרי הקשר, באתר "לא מדויק", 5 במרץ 2015

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

34372218דקדוק חופשי-הקשר