מאגר שאלות ותשובות להוראת מודלים חישוביים:

בניית אוטומט סופי

אסנת אנגלמן, אסתי מאסטראסי, אורנה אברך-שטיין

 

שאלה 1

תהי L שפת כל המילים מעל הא"ב {a,b} אשר ההפרש בהן בין מספר האותיות a למספר האותיות b הוא זוגי.

האם L רגולרית? הוכח את תשובתך!

 

פתרון

ניתן להוכיח כי L רגולרית ע"י בניית אוטומט פשוט שמקבל אותה.

q0 – ההפרש בין מספר האותיות a למספר האותיות b הוא זוגי.

q1 – ההפרש בין מספר האותיות a למספר האותיות b הוא אי-זוגי.

 

 

אמנם, במקרה הכללי לא ניתן לבנות אוטומט עבור שפת הפרשים, כי גם אם ההפרש הדרוש בסוף המילה הוא חסום, הרי אין חסם על ההפרשים תוך כדי קריאת המילה (ראו את הדיון במדריך למורה בפתרון תרגיל 3.14 סעיפים ב' ו-ג').

במקרה זה, בגלל שאנו מתעניינים רק בזוגיות ההפרש, הדבר אפשרי, והאוטומט המתקבל הוא כאמור מאוד פשוט.

שימו לב שהאוטומט זהה לאוטומט המקבל את שפת כל המילים שאורכן זוגי. ואכן במילה שאורכה זוגי, אם מספר האותיות a זוגי אז גם מספר האותיות b זוגי, ואם מספר האותיות a אי-זוגי, אז גם מספר האותיות b אי-זוגי ובכל מקרה ההפרש זוגי. בדומה במילה שאורכה אי-זוגי, אם מספר האותיות a אי-זוגי אז מספר האותיות b זוגי ואם מספר האותיות a זוגי אז מספר האותיות b אי-זוגי ולכן בכל מקרה ההפרש אי-זוגי. לכן השפה המבוקשת היא למעשה שפת כל המילים מעל הא"ב {a,b} שאורכן זוגי.

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים