2011 moed b q 3
Tal (guest) 13 Jul 2012 16:54
היי,
אני לא מצליח להראות שהשפה שנשאלים לגביה היא רגולרית…
נניח קיים NFA שמקבל את השפה.
אזי ניצור אותו באופן זהה ל NFA שראינו בתרגול 2 (יצירת n עותקים של האוטומט המקורי, שכפול כל עותק, רצים בכל עותק על x ובמקביל מנחשים את y וכו').
ההבדל הוא, שבתרגול ראינו y שיכול להיות כל מחרוזת שהיא מעל הא"ב.
בשאלה הנתונה, y צריך להיות קידוד של מ"ט שעוצרת על כל הקלטים מ L1.
אז, נניח שהאוטומט ניחש את y נכונה. עכשיו המכונה האוניברסלית צריכה לסמלץ ריצות של המכונה המקודדת ע"י y על כל הקלטים מ- L1 כדי לוודא ש y ב L2.
L1 אינסופית, לכן המכונה האוניברסלית עלולה לא לעצור… לכן, לא ברור לי מדוע השפה רגולרית.
אשמח לקבל עזרה!
