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