אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי/תרגילים

מכונה עם מצב מקבל יחיד

הראה שלכל מכונה לא דטרמיניסטית $M$ ישנה מכונה $M^{\prime }$ שיש לה מצב מקבל יחיד.

סגירות תחת משלים

נניח ש-$M$ היא מכונה דטרמינסטית. נגדיר את $M^{\prime }$ כמכונה המתקבלת בהחלפת הגדרת המצבים המשלימים והדוחים ב-$M$:

1. הראה שהשפה המתקבלת היא משלימת השפה המקורית.
2. טען מכך שהשפות המתקבלות ע"י מכונה דטרמינסטית סגורות למשלים.

חזור על כך עם מכונה לא דטרמיניסטית:

1. הראה דוגמה בה סעיף 1 הקודם אינו מתקיים.
2. מה תסיק לגבי סגירות השפות המתקבלות ע"י מכונה לא דטרמיניסטית למשלים?

סתם דוגמאות לשפות רגולריות

הראה שהשפות הבאות רגולריות:

1. $\{a^k|k|n\}$ לכל $n$
2. $\{x|x\text{ binary number that divides }n\}$ לכל $n$