מודלים חישוביים-דגשים
אוטומט סופי דטרמיניסטי-
התאמה בה לכל זוג של מצב ואות קלט מותאם מצב יחיד אליו האוטומט עובר
אוטומט סופי דטרמיניסטי-לא מלא-
התאמה בה לכל זוג של מצב ואות קלט מותאם מצב אחד לכל היותר אליו האוטומט עובר. (יתכן שיהיה זוג עבורו לא יהיה מעבר)
אוטומט סופי לא דטרמיניסטי-
התאמה בה לכל זוג של מצב ואות קלט מותאם מצב אליו האוטומט עובר (לכל זוג של מצב ואות קלט יכול להיות יותר ממעבר אחד, ויכול להיות שכלל לא יהיה מעבר)
פעולות על מילים
שרשור-צירוף של מילה אחת בסוף מילה אחרת. לדו' w1w2=aabb w1=aa w2=bb
-יש חשיבות לסדר השרשור!
חזקה-שרשור המילה לעצמה כמספר הפעמים שמופיע במעריך החזקה. לדו': w ,w=ab בשלישית=ababab
היפוך-הפיכת סדר האותיות במילה. לדו': w=abc R(w)=cba
פעולות על שפות
שרשור-שרשור של 2 שפות יוצר שפה המכילה את כל המילים משרשור כל אחת מהמילים בשפה הראשונה לכל אחת מהמילים בשפה השנייה. (ללא כפילויות)
חזקה-שרשור השפה לעצמה כמספר הפעמים שמופיע במעריך החזקה. יוצרת שפה חדשה המכילה את כל המילים שהן שרשור כל אחת מהמילים בשפה עם כל אחת מהמילים בשפה.
היפוך-שפה המכילה את כל המילים ההפוכות למילים בשפה המקורית.
תכונות סגירות על שפות רגולריות
שפה חלקית-שפה המוכלת בשפה שניה (שכל המילים בשפה האחת מוכלות בשפה השנייה)
שפה חלקית לשפה רגולרית אינה בהכרח שפה רגולרית
שפת המשלים-שפת המשלים לשפה מסוימת היא שפה המכילה את כל המילים מעל אותו א"ב אשר אינן מוכלות בשפה.
שפת המשלים של שפה רגולרית היא שפה רגולרית.
שפת האיחוד-בעבור 2 שפות שונות שפת האיחוד של שתי השפות היא שפה המכילה את כל המילים המוכלות לפחות באחת משתי השפות.
שפה המתקבלת מאיחוד שפות רגולריות היא שפה רגולרית.
שפת החיתוך- בעבור 2 שפות שונות שפת האיחוד של שתי השפות היא שפה המכילה את כל המילים המוכלות בשתי השפות. (גם בראשונה וגם בשניה)
שפה המקבלת מחיתוך של שפות רגולריות היא שפה רגולרית.
שפת השרשור-(הבאתי למעלה את ההגדרה)
שפה המתקבלת משרשור של שפות רגולריות היא שפה רגולרית.
שפת ההיפוך-(הבאתי למעלה את ההגדרה)
שפה המקבלת מהיפוך שפה רגולרית היא שפה רגולרית.
אוטומט מחסנית דטרמיניסטי
מודל חישובי להגדרת שפה חופשית הקשר. מילה המתקבלת ע"י אוטומט מחסנית דטרמיניסטי היא מילה אשר בסיום קריאתה נגיע למצב מקבל. מקובל לציין מה צריך להיות מצב המחסנית בסיום המעבר על המילה, אם כי לרוב משתמשים בתנאי שהמחסנית צריכה להיות ריקה בסיום המעבר.
הוכחת רגולריות/אי רגולריות
בהוכחת רגולריות יש לבנות אוטומט סופי
הוכחת אי רגולריות ע"פ הכללם שלמדנו
עם כתוב שיש לנמק-באי רגולריות אפשר להסתפק בנימוק במילים
בנימוק טענות-
נימוק הטוב ביותר הוא לתת מילה הסותרת את הטענה.
נימוק במילים על טענה המורכבת מכמה שפות-יש לנמק למה הטענה נכונה/לא נכונה לכל אחת מהשפות.
שפה שיש בה תלות במניה אבל היא רגולרית
כאשר נראה כי יש תלות במניה בין חלק מהמילה לחלק אחר, אם המשתנה שמסמן את התלות יש לו מספר סופית של מצבים, השפה תהיה רגולרית.
לדו', ניקח את השפה הבאה:
על פניו נראה כי בשפה יש תלות, והיא לא רגולרית.
אבל---
ניקח את המשתנה k .k יכול להיות שווה רק 0 או 1, מכיוון ש n יכול להיות זוגי/אי זוגי. כאשר n יהיה זוגי, k=0, כאשר n אי זוגי, k=1.
כך שאם נחלק את המילים בשפה ל :
1. תחילית המילה
2. סוף המילה
מילה תוכל להסתיים רק באחת מ 2 האופציות הבאות:
K=1 המילה תסתיים ב: bbbbaaa
K=0 המילה תסתיים ב bbaa
כך שנוכל לבנות אוטומט סופי לשפה L2 כי יש בה מספר סופי של מצבים. עבור כל מילה בעלת n אי זוגי נבדוק שהיא מסתיימת בסיומת 1, ועבור כל מילה בעלת n אי זוגי נשתמש בסיומת 2.