אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי/תרגילים
קפיצה לניווט
קפיצה לחיפוש
מכונה עם מצב מקבל יחיד[עריכה]
הראה שלכל מכונה לא דטרמיניסטית ישנה מכונה שיש לה מצב מקבל יחיד.
סגירות תחת משלים[עריכה]
נניח ש- היא מכונה דטרמינסטית. נגדיר את כמכונה המתקבלת בהחלפת הגדרת המצבים המשלימים והדוחים ב-:
- הראה שהשפה המתקבלת היא משלימת השפה המקורית.
- טען מכך שהשפות המתקבלות ע"י מכונה דטרמינסטית סגורות למשלים.
חזור על כך עם מכונה לא דטרמיניסטית:
- הראה דוגמה בה סעיף 1 הקודם אינו מתקיים.
- מה תסיק לגבי סגירות השפות המתקבלות ע"י מכונה לא דטרמיניסטית למשלים?
סתם דוגמאות לשפות רגולריות[עריכה]
הראה שהשפות הבאות רגולריות:
- לכל
- לכל