יום שני, 9 בדצמבר 2013

תרגילים - בנית אוטומטים:

תרגילים - בנית אוטומטים:



1. בנה אוטומט המקבל את כל המילים השייכות לשפה מעל  {a, b, c}   המכילה
    את כל המילים שאינן מכילות את האות c.

2. בנה אוטומט המקבל את כל המילים השייכות לשפה מעל  {a, b, c} המכילות
    בתוכן את האותיות “bcacc”    ברצף אחד.

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

4. בנה אוטומט המקבל את כל המילים השייכות לשפה מעל {a, b, c} המכילה את
    כל  המילים המסתיימות ברצף ab.

5.      שרטט אוטומט המקבל את כל המילים מעל  {1, 0} המכליות בדיוק שני "1"-ם.

6.  בנה אוטומט המקבל את כל המילים מעל הא"ב {a, b, c}  המכילות בין כל שני  b     - ים במילה לפחות c אחד.

7       בנה אוטומט המקבל את כל המילים מעל  {a, b, c }  המכילות את הרצף abb,  
     ואינן מכילות את האות c  לפני שהרצף abb מופיע בפעם הראשונה.

8. בנה אוטומט מעל {a, b, c}   המקבל את כל המילים המכילות את הרצף bc 
    מספר פעמים זוגי.

9. בנה אוטומט המקבל את כל המילים מעל הא"ב {a, b, c} המכילות בסופן את
    הרצף abab.

10. בנה אוטומט המקבל את כל המילים מעל הא"ב {0, 1, 2}  המכילות לפחות
     רצף אחד של 21 , שבינו ובין האות 1 הקרובה ביותר שאחריו יש את הרצף 02.

11. בנה אוטומט המקבל כל המילים מעל {a, b, c}  המכילות  את הרצף babcbac.

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











תרגילים (המשך)


13.    בנה  אוטומטים דטרמיניסטים  סופיים  עבור השפות הבאות מעל
       S = {0, 1, 2}

א.    אוסף כל המילים המתחילות ב ‘01’  ומסתיימות ב ‘0’.

ב.     אוסף כל המילים כך שאחרי כל ‘0’   (אם יש) מופיע מיד  הרצף ‘111’.


14.    בנה אוטומט דטרמיניסטי סופי המקבל את כל המילים W מעל S = {0, 1} המהוות ייצוג בינארי של מספרים המתחלקים ב 4.


15.    בנה את האוטומטים הסופיים הדטרמיניסטים מעל S = {0, 1}

       א.  שפת כל המילים המתחילות   ב ‘1’, או מסתיימות ב ‘010’, או מכילות
             ‘11’.

       ב.  שפת כל המילים  חוץ  מהמילים המכילות ‘11’   או מסתיימות ב ‘010’.


16.    בנה אוטומט סופי דטרמיניסטי עבור השפות הבאות מעל S = {a, b} 

א.    אוסף  המילים שאין בהן a  או  שהן מסתיימות  ב ‘aa’.

ב.     אוסף המילים שאורכן זוגי ומכילות  ‘baa’.

ג.        אוסף המילים המכילות בין 2 ל 4 מופעים של a.

ד.     אוסף המילים בהן ההפרש בין מס" ה ‘a’ ים  ל ‘b’ ים זוגי.


אין תגובות:

הוסף רשומת תגובה