נתונה פעולה הכתובה ב-Java וב-C#:

java
1boolean foo(String str) {
2    int cntrA = 0;
3    int cntrC = 0;
4    for (int i=0; i < str.length; i++) {
5        if (str[i] == 'a') cntrA++;
6        if (str[i] == 'c') cntrC++;
7    }
8    if ((cntrA % 2 == 0) && (cntrC % 3 == 0))
9        return true;
10    return false;
11}

כתוב את השפה L מעל הא"ב {a,c} שהיא אוסף כל המילים שבעבורן הפעולה הנתונה מחזירה true.

בנה אוטומט סופי דטרמיניסטי שיקבל את השפה L.

(אין קשר לסעיף א.)

בנה אוטומט סופי לא דטרמיניסטי מעל הא"ב {a,b} שיקבל את כל המילים המכילות לפחות מופע אחד של אחד מן הרצפים: bbb, aaba, ababa.