בשפות פורמליות, דקדוק חופשי-הקשר (גם: דקדוק חסר הקשר) הוא דקדוק אשר כל כלל יצירה בו הוא מהצורה formula_1 כאשר formula_2 הוא משתנה דקדוקי ואילו formula_3 היא מחרוזת כלשהי של משתנים דקדוקיים וסימנים טרמינליים. דקדוק חסר הקשר יוצר שפה חופשית הקשר (טיפוס 2 בהיררכיה של חומסקי).
המונח "חסר הקשר" מציין כי כלל היצירה עבור formula_2 יכול להתבצע ללא חשיבות לשאלה מה נמצא מימינו ומשמאלו של formula_2, כלומר ללא חשיבות להקשר בו הוא מופיע. בדקדוק תלוי הקשר, לעומת זאת, ייתכנו כללי יצירה מהצורה formula_6, כאשר formula_2 הוא משתנה דקדוקי וformula_8 הן מחרוזות כלשהן של משתנים דקדוקיים וסימנים טרמינליים (ייתכן וריקות).
הגדרה.
דקדוק חסר הקשר formula_9 מוגדר על ידי הרביעייה formula_10, כאשר:
אומרים שהדקדוק formula_9 יוצר מילה formula_18, אם ניתן להתחיל מהמשתנה formula_15, ועל ידי ביצוע אחד או יותר מכללי היצירה שב-formula_13, להגיע אל המילה formula_21. מסמנים במקרה זה formula_22.
השפה הנוצרת על ידי הדקדוק formula_9, היא אוסף כל המחרוזות formula_18, אותן ניתן לייצר מ-formula_15, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,
formula_26
צורה נורמלית.
כל דקדוק חסר הקשר לא ריק שאינו יוצר את המילה הריקה formula_27, ניתן להמרה לדקדוק בו כל כלל יצירה הוא מהצורה formula_28 או formula_29 כאשר formula_30 משתנים ו-formula_31 טרמינל. צורה זו נקראת הצורה הנורמלית של חומסקי על-שם הבלשן נועם חומסקי.
צורה אחרת לדקדוקים חסרי הקשר היא הצורה הנורמלית של גרייבך, הקרויה על-שם מדענית המחשב שילה גרייבך. בדקדוק זה כל כלל יצירה הוא מהצורה formula_32, כאשר formula_31 הוא טרמינל, ו-formula_34 הוא רצף של אפס או יותר משתנים. לצורה זו כמה תכונות מעניינות, שכן כל כלל יצירה מוסיף בדיוק אות אחת למילה נוצרת, ולכן אורך המילה נתון על ידי כמות כללי היצירה שהופעלו. כמו כן, ניתן להמיר כל דקדוק מצורת גרייבך לאוטומט מחסנית שאין בו מעברי-formula_27, ובכך להראות כי תמיד ניתן לבטל מעברי-formula_27 באוטומטי מחסנית.
דו-משמעות.
אם עבור דקדוק נתון קיימות שתי דרכים שונות ליצור מילה מסוימת, אומרים שהדקדוק דו-משמעי. לתכונה זה משמעויות בבלשנות ובקומפילציה. קיימות שפות חסרות הקשר שהן דו-משמעויות בצורה אינהרנטית - כל דקדוק היוצר אותן יהיה דו משמעי. עבור שפות שאינן דו-משמעיות בצורה אינהרנטית, קיים דקדוק שאינו דו-משמעי, אך לא ידועה דרך סיסטמית להמיר דקדוק דו-משמעי לדקדוק שאינו דו-משמעי. נוסף על כך, השאלה האם דקדוק נתון הוא דו-משמעי או לאו אינה כריעה, כלומר לא קיים אלגוריתם שפותר אותה.
באבע מעשה
דקדוק חסר הקשר
אדם מושקא
אדם מוּשְׁקָא (Adam Muszka; 4 במרץ 1914 – ינואר 2005) היה אמן יהודי-פולני-צרפתי, צייר ופסל, ניצול מלחמת העולם השנייה, שחי מרבית שנותיו בפריז ועסק בהנצחת עיירת הולדתו פיוטרקוב טריבונלסקי, הווי החיים שלה, דמויותיה וסופה הטראגי בשואה. הושפע רבות ממרק שאגאל ומפול סזאן, אך יצר סגנון ייחודי ריאליסטי-לירי משלו, שהוגדר על ידי מבקרים פולנים כ"יודאיקה" ייחודית.
תולדותיו.
נולד בעיר פיוטרקוב טריבונלסקי, פולין, ב-1914 כצעיר מבין תשעת ילדי אהרון מושקט, חזן בבית הכנסת הגדול בפיוטרקוב ונכד לחזן עקיבא מושקט-אפטר, שהיה ידוע גם כמלחין ומלחין של ליטורגיה יהודית, בפרט. למד בחדר ולאחר מכן בבית ספר ציבורי פולני.
לאחר שהאב איבד את קולו ומעמדו כחזן, המשפחה עברה לגור בלודז'. בלודז' סיים מושקא את בית ספר התיכון ועבד כפקיד, כדי לתרום להכנסה המשפחתית. במקביל למד בבית הספר העירוני לאמנויות דקורטיביות.
בעת כיבוש פולין הצליח לברוח עם אשתו לטשקנט. ב-1947 חזר לעיר הולדתו פיוטרקוב, ומצא את ביתו ואת עירו בחורבות כשכל תושביה היהודים הושמדו. האירועים הנוראים האלה הותירו את חותמם העז עליו ועל עבודתו. הוא עבר לגור בלודז'. שם יצר וכיהן בתפקיד ראש אגודת האמנים.
לאחר התלבטות ארוכה נענה מושקא לפניית מחלקת התרבות במועצת העיר של פיוטרקוב, שבאותה עת בנתה מחדש את בית הכנסת ההרוס, כספרייה ציבורית, וצייר על התקרה על החיים היהודיים בעיר, כשמעליהם מרחפת ציפור סימבולית בעלת כנפיים שבורות. ב-1955 פיסל את מצבת הזיכרון לנִספי השואה של לודז'. ציור קיר גדול שלו מתנוסס גם במועדון היהודי בלודז'.
ב-1967 הוזמן על ידי עיריית פריז לגור וליצור בה. הוא גר ברובע מונפארנס והיה מעורב מאוד בקרב הקהילה האידישאית הפריזאית עד יום מותו בינואר 2005. היה ידוע גם כפסנתרן מחונן. מושקא היה מיודד עם איציק מאנגער וצייר ציורים בהשראתו, המפורסם שבהם הוא "טווס הזהב". היה קשור גם לדמותו של יאנוש קורצ'אק וצייר את דיוקנו. הרבה להגיע לישראל עם שמחה הולצברג, שהיה ידידו הקרוב.
לכבוד הסכם השלום בין ישראל למצרים, ב- -26 במרץ 1979, השירות הבולאי הישראלי פרסם מעטפת היום הראשון המעוטרת בציורו של מושקא: כינור דוד שממנו פורחות יונות שלום.
ב-1972 הפיקה הטלוויזיה הצרפתית סרט על מושקא בשם "צבעים של זיכרון". הסרט הוקרן ברחבי העולם וגם בישראל בערוץ 1 ב-1973.
יצירותיו הוצגו בתערוכות בעיקר בפולין, בצרפת ובארצות הברית, וב-1977 וב-2008 גם בישראל.
כיום נמצאים ציוריו של מושקא בגלריה הלאומית של ורשה, במוזיאון לודז' לאומנות, במוזיאון להיסטוריה יהודית ובמוזיאון האתנוגרפי של העיר, בגלריה בן אורי בלונדון, בגלריית קלצ'קין בתל אביב, וכן באוספים פרטיים ברחבי העולם.
משפחתו.
היה נשוי לברברה, לבית הימלפרב, ילידת ורשה, ולזוג נולד בלודז' ב-1946 בנם ברוניסלב – כיום יורם מושקט – עורך דין מומחה בתחום התקשורת וקניין רוחני, המתגורר בתל אביב. נכדו דניאל הוא סוכן של הבנק העולמי. ברברה נפטרה בתל אביב ב-12 באוגוסט 2004.
מאשתו השנייה נולדו לו שתי בנות: סוניה, הגרה בצרפת, עובדת בסורבון, ולודמילה, לבורנטית, הגרה בארצות הברית.
חיים מיכל מיכלין
חיים מיכל מִיחלִין (כ"ט בשבט תרכ"ז, פברואר 1867 – י"ט באב תרצ"ז, יולי 1937) היה איש ירושלים, עסקן ציבורי ופעיל בבניית שכונות בירושלים ויישוב ארץ ישראל.
קורות חיים.
נולד בחסלביץ שבאימפריה הרוסית, ובגיל שמונה עלה עם משפחתו לארץ ישראל והתיישב בירושלים, שם עבד אביו כמלמד בתלמוד תורה עץ חיים. מיכלין למד בתלמוד תורה עץ חיים ובישיבת עץ חיים, ומגיל 10 למד במקביל בבית הספר למל ערבית, צרפתית, גרמנית ואנגלית, בעידודו של ראש ישיבת עץ חיים הרב משה נחמיה כהנוב. בשנים 1880-1887 שימש כמזכירו הפרטי של הרב כהנוב ומזכיר ומנהל לשכתו של הרב שמואל סלנט בשנים 1880-1893. כן היה מזכיר של ישיבת עץ חיים ובית החולים ביקור חולים בשנים 1882-1893.
בשנת 1893 עברו מיכלין, חותנו מיכל הכהן וגיסו הרופא ד"ר אליאס כהן לעבוד עבור בית החולים הספרדי משגב לדך ועל רקע זה נוצר קרע בינו לבין מנהלי בית החולים ביקור חולים ועדת האשכנזים ומיכלין עבר לעבוד עבור הרבנים הראשיים הספרדיים החל מהרב יעקב שאול אלישר עד תקופת כהונתו של הרב יעקב מאיר. במסגרת זאת היה מזכיר ראשי של בית החולים משגב לדך, חבר מועצת תלמוד תורה וישיבת תפארת ירושלים, חבר קופת התמחוי ותמיכת אלמנות ויתומים של עדת הספרדים, מייסד וגבאי בית הזקנים הספרדי בירושלים, חבר מזכירות עדת הספרדים בירושלים ושותף בייסוד בית חינוך עיוורים.
בשנת 1905 ייסד ביחד עם אהרן אייזנברג ויצחק לוי את אגודת נטעים ובמשך 25 שנה כיהן בוועד האגודה.
לאחר מאורעות תרפ"ט היה בין מייסדי אגודת יישוב ירושלים העתיקה במטרה לחזק את היישוב היהודי בעיר העתיקה, יחד עם זרח אפרים אפשטיין, יחיאל מיכל טוקצינסקי ואחרים.
במשך ששנים שימש כגבאי ומגיד שיעור בבית הכנסת זיכרון משה בירושלים החדשה.
בשנת ה'תרצ"ד (1934) עבר לפתח תקווה שם עסק בכתיבת ספרי זכרונותיו והיה חבר הנהלת בית הכנסת הגדול "בית יעקב".
בשנת ה'תרצ"ז (1937) במלאת לו שבעים שנה הוציאו מוקיריו לכבודו ספר יובל בשם "תפארת שיבה".
הרב מיכלין נפטר ברמת גן בט"ו באב ה'תרצ"ז, ונקבר בבית הקברות היהודי בהר הזיתים. על שמו רחוב בשכונת בית וגן בירושלים.
מוחמד בועזיזי
טארק א-טייב מוחמד אבן בועזיזי, הידוע גם כמוחמד בועזיזי (בערבית محمد البوعزيزي; 29 במרץ 1984 – 4 בינואר 2011), היה ירקן תוניסאי שהצית את עצמו ב-17 בדצמבר 2010, במחאה על כך שמשטרת תוניסיה סגרה את דוכן הירקות ממנו התפרנס. מעשה מחאה זה היה הזרז שהוביל למהפכה עממית בסוף שנת 2010 ולנפילת השלטון בתוניסיה. מהומות אלו בתוניסיה עוררו תסיסה גם במדינות ערביות נוספות וברחבי העולם.
ביוגרפיה.
בועזיזי נולד בסידי בוזיד שבתוניסיה ב-29 במרץ 1984. אביו, פועל בניין לובי, מת מהתקף לב כאשר בועזיזי היה בן שלוש. אמו של בועזיזי נישאה לדודו של בועזיזי זמן מה לאחר שאביו נפטר.
יחד עם ששת אחיו, בועזיזי התחנך בית הספר בכפר בשם סידי סלאח. במספר כלי תקשורת דווח בזמנו כי בועזיזי היה בעל תואר אקדמי, אך אחותו, סמיה בועזיזי, ציינה כי הוא מעולם לא סיים בית ספר תיכון. בעקבות בריאותו הלקויה של דודו שלא אפשרה לו לעבוד, נאלץ בועזיזי לעבוד בעבודות שונות מאז שהיה בן עשר, ולקראת סוף שנות העשרה נאלץ להפסיק את לימודיו על מנת שיוכל לעבוד במשרה מלאה.