אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "==מכונה עם מצב מקבל יחיד== הראה שלכל מכונה לא דטרמיניסטית <math>M</math> ישנה מכונה <math>M'</math> שיש ..." |
|||
שורה 2:
הראה שלכל מכונה לא דטרמיניסטית <math>M</math> ישנה מכונה <math>M'</math> שיש לה מצב מקבל יחיד.
==סגירות תחת משלים==
נניח ש-<math>M</math> היא מכונה דטרמינסטית. נגדיר את <math>M'</math> כמכונה המתקבלת בהחלפת הגדרת המצבים המשלימים והדוחים ב-<math>M</math>:
#הראה שהשפה המתקבלת היא משלימת השפה המקורית.
# טען מכך שהשפות המתקבלות ע"י מכונה דטרמינסטית סגורות למשלים.
חזור על כך עם מכונה לא דטרמיניסטית:
# הראה דוגמה בה סעיף 1 הקודם אינו מתקיים.
# מה תסיק לגבי סגירות השפות המתקבלות ע"י מכונה לא דטרמיניסטית למשלים?
| |||