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

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

עריכה

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

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

עריכה

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

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

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

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

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

עריכה

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

  1.   לכל  
  2.   לכל