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

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

הראה שלכל מכונה לא דטרמיניסטית $M$ ישנה מכונה $M'$ שיש לה מצב מקבל יחיד.

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

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

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

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

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

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

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

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