שפה חופשית הקשר היא קבוצה של מילים שמיוצרת על ידי כללים פשוטים. דקדוק חסר הקשר הוא קבוצת כללים שמחליפים סימן אחד בכל פעם. ההחלפה לא תלויה במה שמסביב לסימן.
כלל בדקדוק כזה מחליף משתנה בשרשרת של סימנים ומשתנים. כך בונים את כל המילים בשפה.
יש שפה של מחרוזות שבהן יש מספר אחד של אותיות a ואז אותו מספר של אותיות b. לדוגמה: aab b (שני a ואז שני b). שמייצרים אותה עם כלל שמחליף S ב־a S b או ב־a b.
יש שפה שמורכבת מאותיות a, b ו־c באותו מספר בכל פעם. אותה שפה אי אפשר לייצר עם הכללים האלה. אפשר להראות זאת בהוכחה מתמטית שנקראת למת הניפוח (כלי שמראה מי אפשר למתח).
שפות חופשיות ההקשר סגורות תחת איחוד. איחוד זה לחבר שתי שפות ביחד. הן גם סגורות תחת שרשור. שרשור זה לשים שתי מילים אחת אחרי השנייה. הן לא סגורות תחת חיתוך והפרש. חיתוך אומר למצוא מילים שנמצאות בשתי השפות. הפרש אומר לקחת מילים שבאחת השפה אבל לא בשנייה.
יש שאלות על שפות אלה שמחשבים לא יכולים להכריע תמיד. לשפות רגולריות יש פתרונות פשוטים יותר.
כלל בדקדוק כזה מחליף משתנה בשרשרת של סימנים ומשתנים. כך בונים את כל המילים בשפה.
יש שפה של מחרוזות שבהן יש מספר אחד של אותיות a ואז אותו מספר של אותיות b. לדוגמה: aab b (שני a ואז שני b). שמייצרים אותה עם כלל שמחליף S ב־a S b או ב־a b.
יש שפה שמורכבת מאותיות a, b ו־c באותו מספר בכל פעם. אותה שפה אי אפשר לייצר עם הכללים האלה. אפשר להראות זאת בהוכחה מתמטית שנקראת למת הניפוח (כלי שמראה מי אפשר למתח).
שפות חופשיות ההקשר סגורות תחת איחוד. איחוד זה לחבר שתי שפות ביחד. הן גם סגורות תחת שרשור. שרשור זה לשים שתי מילים אחת אחרי השנייה. הן לא סגורות תחת חיתוך והפרש. חיתוך אומר למצוא מילים שנמצאות בשתי השפות. הפרש אומר לקחת מילים שבאחת השפה אבל לא בשנייה.
יש שאלות על שפות אלה שמחשבים לא יכולים להכריע תמיד. לשפות רגולריות יש פתרונות פשוטים יותר.
עדיין אין תגובות. היה הראשון להגיב!
תגובות גולשים