אוטומט סופי אי־דטרמיניסטי דומה לאוטומט הדטרמיניסטי, אלא שפונקציית המעברים מוגדרת באופן שונה.
באוטומט האי-דטרמיניסטי, עבור כל מצב formula_1 ואות formula_2 עשויים להיות מספר כלשהו (גם 0) של מצבים אליהם יכול האוטומט לעבור כאשר הוא נמצא במצב formula_1 והאות שהוא קורא מן הקלט היא formula_2. במודלים מסוימים, פונקציית המעברים מאפשרת מעברים בין מצבים מסוימים ללא קריאת אף אות מן הקלט (מעברי-formula_13). כתוצאה מכך, עשויות להיות מספר ריצות שונות של האוטומט על מילת קלט מסוימת. מבחינה פורמלית, מילה תתקבל אם ורק אם קיימת ריצה של האוטומט שמסתיימת במצב מקבל כלשהו, גם אם קיימת ריצה אחרת שמסתיימת במצב שאינו מקבל, או כזו ש"נתקעת" משום שהגיעה למצב שממנו אין אף מעבר אפשרי עבור האות שנקראת מן הקלט.
לפי ההגדרה, כל אוטומט סופי דטרמיניסטי הוא בפרט גם אוטומט סופי אי-דטרמיניסטי. בכיוון ההפוך, ניתן להוכיח כי כל אוטומט סופי אי־דטרמיניסטי שקול לאוטומט סופי דטרמיניסטי. כלומר, היעדר הדטרמיניזם אינו מוסיף לכוחו החישובי של האוטומט הסופי (בשונה מאשר במודל של אוטומט מחסנית, לדוגמה).
שפות המתקבלות על ידי אוטומט סופי נקראות שפות רגולריות ונוצרות על ידי דקדוקים רגולריים וביטויים רגולריים.
אוטומטי-formula_14.
ישנם מודלים של אוטומטים סופיים מעל עצמים אינסופיים (למשל, מילים אינסופיות, כלומר סדרות אינסופיות של אותיות מהאלפבית).
כתוצאה מכך, אין אפשרות להגדיר קבלה של מילה בהתאם למצב שבו נמצא האוטומט בסיומה של הריצה, משום שזו לא מסתיימת.
קיימים מודלים שונים שמגדירים קבלה של מילים אינסופיות.
למשל, באוטומט בוקי (Büchi) תנאי הקבלה מגדיר קבוצת מצבים מקבלים, ומילה מתקבלת אם ורק אם היא מבקרת במצב מקבל אינסוף פעמים.
באוטומט רבין תנאי הקבלה מורכב מזוגות של קבוצות formula_15 כאשר ריצה היא מקבלת אם קיים זוג formula_16 שעבורו קבוצת המצבים formula_17 שבהם מבקרת הריצה אינסוף פעמים מקיימת
formula_18
formula_19,
כלומר הריצה מבקרת אינסוף פעמים במצב מ-formula_20 ומבקרת רק מספר סופי של פעמים בכל מצבי formula_21. מלבד שני מודלים אלו קיימים מודלים רבים נוספים אשר מגדירים את אופן קבלת המילים על ידי האוטומט.
שלא כמו במקרה של אוטומטים סופיים מעל מילים סופיות, שבו קיימת שקילות בין המודלים הדטרמיניסטי והאי-דטרמיניסטי, אין שקילות כזו בהקשר של אוטומט בוקי. קיימות שפות פשוטת שעבורן קיים אוטומט בוקי אי-דטרמיניסטי, אבל לא קיים אוטומט דטרמיניסטי שקול (למשל, שפת כל המילים שמכילות רק מספר סופי של אות נתונה). במקרה של אוטומט רבין כן קיימת שקילות כזו. יותר מכך, לכל אוטומט בוקי קיים אוטומט רבין שקול.
מייק לי
מייק לי (באנגלית: Mike Leigh; נולד ב-20 בפברואר 1943) הוא במאי קולנוע, מחזאי, ובמאי תיאטרון יהודי-בריטי, עטור פרסים, הנחשב על ידי מבקרים ואנשי קולנוע כבמאי הקולנוע הבריטי החשוב ביותר כיום.
קורות חיים.
לי נולד בסאלפורד, במנצ'סטר רבתי שבחבל לנקשייר, למשפחה יהודית ששמה המקורי היה "ליברמן" והוא אונגלז ב-1939 בשביל להימנע מהאנטישמיות באותה העת. הוא למד ב-RADA האקדמיה המלכותית לאמנויות הבמה ובבית ספר למשחק באסקס, מאוחר יותר השלים את השכלתו הקולנועית בבית הספר לקולנוע בלונדון.
את ניסיונו הראשון כבמאי ושחקן רכש ב"רויאל שייקספיר קומפני" (RSC). בהמשך פרש ממשחק והתמקד בכתיבה ובימוי, לתיאטרון, טלוויזיה וקולנוע.
בשנים האחרונות הוא פועל בעיקר בקולנוע, תחום שבו זכה להכרה בינלאומית רחבה.
לי היה אמור לבקר בישראל בנובמבר 2010, כאורח בית הספר סם שפיגל לקולנוע ולטלוויזיה, אך ביטל את ביקורו בשל אישור תיקון לחוק האזרחות על ידי ממשלת ישראל. במכתב שכתב, הוא מציין שאין בכוונתו להגיע לישראל עד אשר יינתן פתרון הוגן לפלסטינים. ב-2019 הוא ואמנים בריטים נוספים כמו פיטר גבריאל ורוג'ר ווטרס קראו להחרים את האירוויזיון בישראל.
יצירתו.
כללי.
מייק לי הוא יוצר קולנוע ותיאטרון ריאליסטי.
סרטיו ומחזותיו, הם דרמות ריאליסטיות העוסקות בחייהם הרגילים והיומיומיים של אנטי גיבורים בני המעמד הבינוני הנמוך (יצירותיו המוקדמות), ובני מעמד הפועלים (יצירותיו המאוחרות).
בניגוד לבמאי הקולנוע קן לואץ', אליו נוהגים להשוותו, לי, אינו במאי בעל אג'נדה פוליטית מוגדרת, אשר סרטיו משמשים כאמצעי לבטאה. האג'נדה שלו היא הומנית עם נגיעות חברתיות. להוציא סרטו "עירום" ודרמת הטלוויזיה ""Meantime", שבהם גיבוריו עומדים מחוץ לסדר החברתי ומורדים בו ו"Four Days In July"" המתאר את החיים בצילה של המלחמה בבלפסט, עיקר העניין של לי ככותב וכבמאי הן הדמויות - אופיין, חייהן, רגשותיהן והיחסים שהם מנהלים עם אחרים.
תיאטרון, טלוויזיה וקולנוע.
לי כתב וביים כ-20 מחזות לתיאטרון האנגלי. המפורסם בהם הוא "המסיבה של אביגייל" ("Abigail's Party") שהועלה על הבמה ב-1977 והוסרט ל"תיאטרון הכורסה" של ה-BBC. המחזה הוא קומדיה עוקצנית על חייה של משפחה זעיר בורגנית, והוצג על במות רבות ברחבי העולם, כולל הפקה בישראל בסטודיו למשחק ניסן נתיב ב-2004. ב-2002, ביובל ה-25 להפקת המקור הוא הועלה בלונדון, וזכה למועמדות לפרס על שם לורנס אוליבייה על החידוש התיאטרלי המוצלח של השנה.
ב-2005, אחרי 12 שנים של שתיקה תיאטרלית, חזר לי לבמה עם מחזה חדש, "אלפיים שנות" ("Two Thousand Years"). במחזה, שמספר את סיפורם של שלושה דורות במשפחה יהודית לונדונית, השתמש לי לראשונה בשורשיו היהודים ואפילו שילב את הזווית הישראלית בדמותו של צעיר ישראלי, בן זוגה של אחת מבנות המשפחה. המחזה זכה להצלחה גדולה בקופות ולבקורות מעורבות: שבחים למשחק המעולה ולעבודת הבימוי, לצד התייחסות ביקורתית למחזה עצמו.
ב-1971, ביים את סרטו הראשון "רגעי עצב" ("Bleak Moments"), ומשלא קיבל הזדמנות לביים סרט קולנוע נוסף, פנה לטלוויזיה, אשר בה פעלו באותה תקופה במאים איכותיים נוספים כמו קן לואץ' וסטיבן פרירס. הוא כתב וביים דרמות בעיקר עבור ה-BBC. בהם: ""Grown-Ups" הקומי, שהוקרן ב-1980 ומספר את סיפורו של זוג החי בקנטרברי, משפחתם, חבריהם ושכניהם.
"Home Sweet Home" המלנכולי יותר, הוקרן ב-1984 ומספר על כישלון ליצור קשר ועל בדידות דרך תיאור חייהם של שלושה דוורים ומשפחותיהם.
"Meantime"" הוסרט ב-1984 עבור ערוץ 4 והוא סרט הטלוויזיה הפוליטי ביותר של לי. הוא מספר על קשר אמיץ בין שני אחים בשנות העשרים לחייהם, החיים עם הוריהם במזרח לונדון ומתאר את היאוש של דור שלם של צעירים מובטלים באנגליה תחת שלטונה של מרגרט תאצ'ר.
ב-1988, 17 שנים לאחר סרט הקולנוע הקודם שלו, חזר לי לתעשיית הקולנוע וזכה להצלחה והכרה, כולל מועמדויות לפרס אוסקר ופרסים בפסטיבל קאן ואחרים (ראו פרסים ומועמדויות).
סרטי הקולנוע שלו, הם המשך ישיר של יצירתו עד כה, עם העברת המיקוד למעמד הפועלים והעמקת יכולת ההבנה האנושית.
סרטיו הידועים ביותר:
ב-6 באוקטובר 2010 הוצג בפסטיבל הסרטים בניו יורק סרטו החדש "עוד שנה", העוקב אחר התרחשויות במשך עונות השנה במשפחה חמימה תוך בחינת יחסיה עם חבריה הבודדים. מייק לי כתב וביים. שחקנים ראשיים ג'ים ברודבנט, לסלי מנוויל, רות שין.
פרסים ומועמדויות.
מייק לי זכה, עבור סרטי הקולנוע שלו, באין ספור פרסים ומועמדויות ברחבי העולם, בפסטיבלים ומטעם ארגוני מבקרים ידועים יותר וידועים פחות. הרשימה להלן כוללת את פירוט הפרסים המוכרים ביותר.
פילמוגרפיה.
דרמות טלוויזיה.
כל הדרמות להוציא "Meantime" הוסרטו עבור ה-BBC.
"Meantime" הוסרט עבור Channel Four.
הרי האפנינים
הרי האפּנינים (איטלקית: Appennini, לטינית: Appenninus, יוונית: Απεννινος) הם רכס הרים המשתרעים לאורך חופה המזרחי של איטליה, מצפונה לדרומה, אורכם 1,200 קילומטרים והם מהווים את "עמוד השדרה" הגאוגרפי של המדינה. המסלע העיקרי של ההרים הוא אבן גיר.
היווצרות.
הרכס הוא רכס עתיק בן לפחות 65 מיליוני שנים על פי ההערכות. על פי השערות של מדענים הרכס עלה והתגבש לקראת סוף תור הקרטיקון. תהליך זה התרחש כשהלוח האפריקאי החל להתנגש בעדינות בלוח האירו-אסיאתי. באותו אירוע טקטוני נוצרו גם הרי האלפים. הרי הרכס מורכבים בעיקר משכבות שמקורן בתור השלישון ובעידן המזוזואיקון.
מקור השם.
מקור השם "אפנינים" עשוי לנבוע מהשורש הלטיני "penne" שמשמעותו היא נוצת קולמוס. מקור נוסף לשם עשוי להיות שמו של רכס הרים הקרוי הפנינים (אנגלית: Pennines), רכס הרים נמוך המשתרע מדרום סקוטלנד לצפון אנגליה, במרכזו של האי בריטניה הגדולה.
עד המאה ה-3 לפני הספירה השם התייחס לחלקו הצפוני של הרכס בלבד, המשתרע המאלפים הדרום מערביים ועד לאנקונה. פוליביוס היה הראשון כנראה שהגדיר את כל הרכס בשם זה.
גאוגרפיה.
חצי האי האפניני, המהווה את מרבית שטחה של איטליה, נקרא על שם ההרים האלה. ההרים מיוערים וירוקים ברובם, אך בימים עברו היו ירוקים ומיוערים עוד יותר. פליניוס הזקן מספר בעיקר על עצי אלון, אורן ואשור. הגורם לצמצום משמעותי בכמות הוא כריתת עצים אך הממשלה האיטלקית החלה במהלכים של ייעור מחדש בהרים אלה. הפסגה הגבוהה ביותר נקראת הר גראן סאסו (2,912 מטרים), והיא מכוסה בחלקה בקרחון הדרומי ביותר באירופה. הפסגות הגבוהות ביותר מכוסות קרח כמעט כל השנה. הפסגה המוכרת הנמוכה ביותר היא בגובה של 1,525 מטרים ושמה הוא הר נרון.
המורדות המזרחיים של ההרים, הפונים לכיוון הים האדריאטי, הם תלולים, בעוד שהמורדות המערביים מהווים מישור שעליו שוכנות מרבית הערים ההיסטוריות של איטליה.
בעלי חיים.