שאלות על ביטויים רגולריים

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

עבורנו, התחביר של ביטויים רגולריים הוא כדלקמן:

• לכל אות a בא״ב, a הוא ביטוי רגולרי.
• e הוא ביטוי רגולרי, המייצג את המילה הריקה.
• O הוא ביטוי רגולרי, המייצג את השפה הריקה.
• S הוא ביטוי רגולרי, המייצג אות כלשהי בא״ב.
• אם r ביטוי רגולרי אז גם (r) ו-r*‎ הם ביטויים רגולריים.
• אם r ו-s הם ביטויים רגולריים אז גם rs ו-r+s הם ביטויים רגולריים.

ניתן להשתמש גם ברווחים.

ניתן לראות דוגמה בשאלה הראשונה, בה נתנו גם את הפתרון.

כל השאלות הראשונות לקוחות מהשאלון הקודם.

הערה: דף זה מונגש בצורה בסיסית בלבד. סטודנט שנתקל בבעיות מתבקש לפנות לצוות הקורס.

1. בנו ב״ר מעל הא״ב {a,b} שמקבל את שפת כל המילים בהן לפחות אות אחת מופיעה לפחות פעמיים (שאלה מתרגול 10):

   S*(aS*a+bS*b)S*

   בדיקה

2. בנו ב״ר מעל הא״ב {a,b} שמקבל את שפת כל המילים הלא-ריקות שמתחילות ומסתיימות באותה אות:

   בדיקה

3. בנו ב״ר מעל הא״ב {a,b,c} שמקבל את שפת כל המילים הלא-ריקות בהן האות האחרונה מופיעה רק פעם אחת במילה:

   בדיקה

4. בנו ב״ר מעל הא״ב {a,b,c} שמקבל את שפת כל המילים המסתיימות בשתי אותיות זהות:

   בדיקה

5. בנו ב״ר מעל הא״ב {a,b} שמקבל את שפת כל המילים שאורכן מתחלק ב-3, או מספר ה-a-ים בהן זוגי, או מספר ה-b-ים בהן אי-זוגי:

   בדיקה

6. בשאלה זו, עליכם לבנות ב״ר המתאר את שפת כל המכפלות של מספרים חוקיים.

   האלפבית מורכב מכל הספרות ומהסימן x.

   מספר הוא חוקי אם הוא 0, או שספרתו השמאלית ביותר אינה 0. במילים אחרות, איננו מרשים מספרים בסגנון 01.

   דוגמאות למילים חוקיות בשפה: 10, 0x3, 4x5x6.

   בדיקה

7. בנו ב״ר מעל הא״ב {a,b,c} שמקבל את שפת כל המילים כך שבין כל מופע של האות b לבין כל מופע של האות a, מופיעה האות c לפחות פעם אחת:

   בדיקה

8. בנו ב״ר מעל {a,b} שמקבל את שפת כל המילים המכילות מספר זוגי של a-ים ושל b-ים: (קשה!)

   בדיקה