שפה חופשית הקשר

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