בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.
עמוד 11, סעיף ב(2): אוטומט סופי דטרמיניסטי שאינו מלא, מצבים q0–q10, חלק מסימני הקלט חסרים
deterministic, NOT-complete finite automaton, states q0 .. q10 (q0 is the leftmost, no incoming arrow drawn).
Transitions that DO carry a printed input symbol:
q0 -> q1 labelled a
q1 -> q3 labelled b
q1 -> q2 labelled a
q2 -> q5 labelled b
q5 -> q7 labelled c
Transitions drawn WITHOUT a symbol (these are the ones the student must fill in):
q2 -> q1
q3 -> q4 and q4 -> q3 (two separate parallel arrows)
q4 -> q8
q7 -> q8
q8 -> q9 and q9 -> q8 (two separate parallel arrows)
q5 -> q6 and q6 -> q5 (two separate parallel arrows)
q3 -> q10 (long line to the right)
q6 -> q10 (long line to the right)
q10 -> q10 (self loop)
No accepting state is marked anywhere in the drawing.
לפניכם שלוש שפות מעל הא"ב {a , b}: L1 = { aⁿ bᵐ aᵏ | n, m, k > 0, n = k } L2 = { aⁿ bᵐ aᵏ | n, m, k > 0, n % 2 = k % 2 } L3 = { aⁿ bᵐ aᵏ | n, m, k > 0, n+m+k < 100 } לפניכם ארבעה סעיפים (1)–(4). ענו על כולם (בנימוק מספיק הסבר מילולי, אין צורך באוטומט).
בנוגע לכל אחת מן השפות L1 – L3 , כתבו אם היא רגולרית או לא רגולרית. נמקו את תשובתכם.
האם השפה L1 ∩ L3 רגולרית? נמקו את תשובתכם.
האם השפה L1 ∩ ‾L3 רגולרית? נמקו את תשובתכם.
האם השפה L2 ∩ ‾L3 רגולרית? נמקו את תשובתכם.
נתונה השפה L מעל הא"ב {a,b,c} : L = {aᵐ bᵏ cˣ | m, k, x > 0 וגם (m%2 = k%2 או m%2 = x%2)} הסבר: השפה L מכילה מילים שבהן כל אחת מן האותיות abc מופיעה פעם אחת לפחות, ולפי סדר זה (המופעים של a תחילה ואחר כך של b ואחר כך של c). כמו כן, אם מספר המופעים של האות a הוא זוגי/אי־זוגי, מספר המופעים של האות b או של האות c יהיה גם הוא זוגי/אי־זוגי בהתאמה. דוגמה למילה בשפה L היא abbbbccc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא אי־זוגי, וכך גם מספר המופעים של האות c . דוגמה נוספת למילה בשפה L היא aaaabbc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא זוגי, וכך גם מספר המופעים של האות b . דוגמה למילה שאינה בשפה L היא aabc . אומנם כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, אך מספר המופעים של האות a הוא זוגי, ואילו מספר המופעים של האות b ושל האות c הוא אי־זוגי.
לפניכם חמש מילים: abbcc , abcc , bbc , abc , abbac . העתיקו כל אחת מן המילים למחברתכם, וקבעו אם היא שייכת לשפה L או לא שייכת לשפה L . נמקו את קביעותיכם.
נתון לפניכם אוטומט סופי דטרמיניסטי שאינו מלא המקבל את השפה L . באוטומט קיימים כל המצבים וכל המעברים הנדרשים, אך בכמה מן המעברים חסרים סימני הקלט (התווים במעברים), והמצבים המקבלים באוטומט אינם מסומנים כלל. העתיקו את האוטומט למחברתכם, הוסיפו את סימני הקלט החסרים, וסמנו את המצבים המקבלים. הערה: האוטומט צריך להישאר סופי דטרמיניסטי שאינו מלא. אין להוסיף בו מצבים או מעברים, ואין לשנות את סימני הקלט המופיעים בו. תשובה שתהיה בה שינוי באוטומט הנתון לא תזוכה בנקודות. [האוטומט ב-figures]
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.