לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

[עריכה]

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

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

[עריכה]

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

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

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

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

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

[עריכה]

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

  1. לכל
  2. לכל