לפניכם השפה L מעל הא"ב {0, $}:
L = { 0^3 $ 0^{i_1} $ 0^{i_2} $ … 0^{i_k} $ | k ≥ 1, ולכל m בין 1 ל-k: i_m ≥ 0 ו-i_m מתחלק ב-3 ללא שארית }
כלומר: כל מילה מתחילה ב-000 ואחריה $, ולאחר מכן מופיעים k רצפים (k ≥ 1), שכל אחד מהם הוא רצף של אפסים שאורכו מתחלק ב-3 (ייתכן גם אורך 0) ואחריו $.
כתבו את המילה הקצרה ביותר בשפה L.
בנו אוטומט סופי דטרמיניסטי שיקבל את השפה L.
לפניכם השפה L מעל הא"ב {0, $}:
L = { 0^3 $ 0^{i_1} $ 0^{i_2} $ … 0^{i_k} $ | k ≥ 1, ולכל m בין 1 ל-k: i_m ≥ 0 ו-i_m מתחלק ב-3 ללא שארית }
כלומר: כל מילה מתחילה ב-000 ואחריה $, ולאחר מכן מופיעים k רצפים (k ≥ 1), שכל אחד מהם הוא רצף של אפסים שאורכו מתחלק ב-3 (ייתכן גם אורך 0) ואחריו $.
כתבו את המילה הקצרה ביותר בשפה L.
בנו אוטומט סופי דטרמיניסטי שיקבל את השפה L.