דוגמה

\Sigma=\left\{ a \right\} \qquad L=\left\{ a \right\}

הגדרה 1 (סגור קלין)

בהינתן שפה $L$ , נגדיר סגור קלין של $L$ בתור:

L^*=\bigcup_{i=0}^\infty L^i

הגדרה 2 (סגור חיובי)

בהינתן שפה $L$ , נגדיר את הסגור החיובי בתור:

L^+=\bigcup_{i\geq 1}^\infty L^i

למה (למת השרשור)

יהי $A=(Q,\Sigma,q_{0},\delta,F)$ אוטומט סופי דרמיניסטי.
לכל $u,v \in\Sigma^*$ ולכל $q \in Q$ מתקיים:

\delta^*(q,u \circ v)=\delta^*(\delta^*(q,u),v)

הערה

לא נוכיח את הטענה אבל ניתן להשתמש בה בתרגילי הבית ובמבחן.

הגדרה 3 (שפת המצב)

בניגוד לשפת האוטומט שראינו בהרצאה, שפה של מצב $q$ מוגדרת כך:

L(q)=\left\{ w \in \Sigma^*|\delta^*(q_{0},w)=q \right\}

כלומר, כל המילים שהריצה של $A$ מעליהן מ- $q_{0}$ מסתיימת במצב $q$ .

משפט

\underbracket{L(A)}_{\R{\text{שפת האוטומט}}}=\bigcup_{q \in F}L(q)

תרגול

תרגיל

יהא $A$ האוטומט הבא:

הוכיחו כי $L(A)=\left\{ 01 \right\}^*$ .

הערה

נשים לב כי $\left\{ 0,1 \right\}^*\neq\left\{ 01 \right\}^*$ שכן הימני הוא רצפים של $01$ בעוד שהשמאלי הוא כל המילים הנוצרות מ- $0$ ו- $1$ .

הוכחה:
כדי להוכיח את השוויון נראה כי לכל $w \in \left\{ 0,1 \right\}^*$ מתקיים:

w \in \left\{ 01 \right\}^* \iff w \in L(A)

ישירות מהגדרת שוויון קבוצות.
נשים לב כי $w \in L(A)$ ⇔ (מהגדרת שפת DFA) $\delta^*(q_{0},w)\in F$ ⇔ ( $q_{0}$ מצב מקבל יחיד) $\delta^*(q_{0},w)=q_{0}$ ⇔ (הגדרת שפת מצב) $w \in L(q_{0})$ .
לכן, מספקיל להוכיח כי לכל $w \in \left\{ 0,1 \right\}^*$ מתקיים: $w \in \left\{ 01 \right\}^* \iff w \in L(q_{0})$ .
נוכיח באינדוקציה כי:

מתקיים: $L(q_{0})=\left\{ 01 \right\}^*$
מתקיים: $L(q_{1})=\left\{ 01 \right\}^* \circ \left\{ 0 \right\}$ .

בסיס: כאשר $w=\epsilon$ , כלומר, $|w|=0$ .
מתקיים כי $\epsilon \in \left\{ 01 \right\}^*$ . בנוסף, $\delta^*(q_{1},\epsilon)=q_{0}$ מהגדרת $\delta^*$ , ולכן מהגדרת שפת מצב $\epsilon \in L(q_{0})$ . ⇐ טענה 1 מתקיימת באופן ריק.
מתקיים כי $\delta^*(q_{0},\epsilon)=q_{0}\neq q_{1}$ . לכן, $\epsilon \not\in L(q_{1})$ . בנוסף, $\epsilon \not\in \left\{ 01 \right\}^*\circ\left\{ 0 \right\}$ כי $\epsilon$ לא מסתיימת ב- $0$ ולכן הטענה 2 מתקיימת באופן ריק.

צעד: נניח את נכונות טענות 1 ו-2 לכל מילה $w$ באורך $n$ ונראה למילה $u$ מאורך $n+1$ .
נסמן $u=w\sigma$ עבור $w \in\Sigma^*$ מאורך $n$ ו- $\sigma \in\Sigma$ .

u \in \left\{ 01 \right\}^* \underset{\R{\text{מבנה המילה}}}{\iff} w \in \left\{ 01 \right\}^*\circ\left\{ 0 \right\} \land \sigma=1 \underset{\R{\text{הנחת האינדוקציה}}}{\iff} w \in L(q_{1}) \land \sigma=1\underset{\R{\text{מבנה האוטומט}}}{\iff} u \in L(q_{0})

הערה (הסבר לשלב האחרון שלא צריך לכתוב)

⇐: מניחים $\sigma=1$ ו- $w \in L(q_{1})$ . ולכן:

\delta^*(q_{0},u)=\delta^*(q_{0},w\sigma)=\delta(\delta^*(q_{0},w),\sigma)=\delta(q_{1},1)=q_{0}

⇒: מניחים $u \in L(q_{0})$ . זה אומר ש- $\delta^*(q_{0},u)=q_{0}$ (לפי הגדרת שפת מצב)

q_{0}=\delta^*(q_{0},w\sigma)=\delta(\delta^*(q_{0},w),\sigma)

ישנה רק דרך אחת להגיע ל- $q_{0}$ בקריאת אות, והיא כאשר $\sigma=1$ ו- $\delta^*(q_{0},w)=q_{1}$ .

כעת, נעבור להוכחת הטענה השנייה:

u \in \left\{ 01 \right\}^* \circ \left\{ 0 \right\} \underset{\R{\text{מבנה u}}}{\iff} w \in \left\{ 01 \right\}^* \land \sigma=0 \underset{\R{\text{הנחת האינדוקציה}}}{\iff} w \in L(q_{0}) \land \sigma=0

\underset{\R{\text{הגדרת שפת מצב}}}{\iff} \delta^*(q_{0},w)=q_{0} \land \sigma=0 \underset{\R{\text{מבנה האוטומט}}}{\iff} \delta^*(q_{0},u)=\delta(\delta^*(q_{0},w),\sigma)=q_{1}

\underset{\R{\text{הגדרת שפת מצב}}}{\iff} u \in L(q_{1})

∎

תרגיל

בנו DFA עבור שפת המילים שמתחילות ב- $a$ ומכילות מספר אי זוגי של $b$ מעל $\Sigma=\left\{ a,b \right\}$ .

הוכחה:

∎

תרגיל

בנו DFA עבור שפת המילים המכילות את הרצף $ab$ .

הוכחה:

∎

תרגיל

הוכיחו/הפריכו את הטענה הבאה:

u \in L_{1} \land v \in L_{2} \iff u \circ v \in L_{1} \circ L_{2}

הוכחה:
⇒: נכון לפי הגדרת $L_{1} \circ L_{2}$ .
⇐: נסתכל על דוגמה נגדית:

L_{1}=\left\{ aab \right\},\; L_{2}=\left\{ bba \right\}

u=a,v=abbba

∎

דוגמה

\Sigma=\left\{ a \right\} \qquad L=\left\{ a \right\}

הגדרה 1 (סגור קלין)

בהינתן שפה $L$ , נגדיר סגור קלין של $L$ בתור:

L^*=\bigcup_{i=0}^\infty L^i

הגדרה 2 (סגור חיובי)

בהינתן שפה $L$ , נגדיר את הסגור החיובי בתור:

L^+=\bigcup_{i\geq 1}^\infty L^i

למה (למת השרשור)

יהי $A=(Q,\Sigma,q_{0},\delta,F)$ אוטומט סופי דרמיניסטי.
לכל $u,v \in\Sigma^*$ ולכל $q \in Q$ מתקיים:

\delta^*(q,u \circ v)=\delta^*(\delta^*(q,u),v)

הערה

לא נוכיח את הטענה אבל ניתן להשתמש בה בתרגילי הבית ובמבחן.

הגדרה 3 (שפת המצב)

בניגוד לשפת האוטומט שראינו בהרצאה, שפה של מצב $q$ מוגדרת כך:

L(q)=\left\{ w \in \Sigma^*|\delta^*(q_{0},w)=q \right\}

כלומר, כל המילים שהריצה של $A$ מעליהן מ- $q_{0}$ מסתיימת במצב $q$ .

משפט

\underbracket{L(A)}_{\R{\text{שפת האוטומט}}}=\bigcup_{q \in F}L(q)

תרגול

תרגיל

יהא $A$ האוטומט הבא:

הוכיחו כי $L(A)=\left\{ 01 \right\}^*$ .

הערה

נשים לב כי $\left\{ 0,1 \right\}^*\neq\left\{ 01 \right\}^*$ שכן הימני הוא רצפים של $01$ בעוד שהשמאלי הוא כל המילים הנוצרות מ- $0$ ו- $1$ .

הוכחה:
כדי להוכיח את השוויון נראה כי לכל $w \in \left\{ 0,1 \right\}^*$ מתקיים:

w \in \left\{ 01 \right\}^* \iff w \in L(A)

מתקיים: $L(q_{0})=\left\{ 01 \right\}^*$
מתקיים: $L(q_{1})=\left\{ 01 \right\}^* \circ \left\{ 0 \right\}$ .

u \in \left\{ 01 \right\}^* \underset{\R{\text{מבנה המילה}}}{\iff} w \in \left\{ 01 \right\}^*\circ\left\{ 0 \right\} \land \sigma=1 \underset{\R{\text{הנחת האינדוקציה}}}{\iff} w \in L(q_{1}) \land \sigma=1\underset{\R{\text{מבנה האוטומט}}}{\iff} u \in L(q_{0})

הערה (הסבר לשלב האחרון שלא צריך לכתוב)

⇐: מניחים $\sigma=1$ ו- $w \in L(q_{1})$ . ולכן:

\delta^*(q_{0},u)=\delta^*(q_{0},w\sigma)=\delta(\delta^*(q_{0},w),\sigma)=\delta(q_{1},1)=q_{0}

⇒: מניחים $u \in L(q_{0})$ . זה אומר ש- $\delta^*(q_{0},u)=q_{0}$ (לפי הגדרת שפת מצב)

q_{0}=\delta^*(q_{0},w\sigma)=\delta(\delta^*(q_{0},w),\sigma)

ישנה רק דרך אחת להגיע ל- $q_{0}$ בקריאת אות, והיא כאשר $\sigma=1$ ו- $\delta^*(q_{0},w)=q_{1}$ .

כעת, נעבור להוכחת הטענה השנייה:

u \in \left\{ 01 \right\}^* \circ \left\{ 0 \right\} \underset{\R{\text{מבנה u}}}{\iff} w \in \left\{ 01 \right\}^* \land \sigma=0 \underset{\R{\text{הנחת האינדוקציה}}}{\iff} w \in L(q_{0}) \land \sigma=0

\underset{\R{\text{הגדרת שפת מצב}}}{\iff} \delta^*(q_{0},w)=q_{0} \land \sigma=0 \underset{\R{\text{מבנה האוטומט}}}{\iff} \delta^*(q_{0},u)=\delta(\delta^*(q_{0},w),\sigma)=q_{1}

\underset{\R{\text{הגדרת שפת מצב}}}{\iff} u \in L(q_{1})

∎

תרגיל

בנו DFA עבור שפת המילים שמתחילות ב- $a$ ומכילות מספר אי זוגי של $b$ מעל $\Sigma=\left\{ a,b \right\}$ .

הוכחה:

∎

תרגיל

בנו DFA עבור שפת המילים המכילות את הרצף $ab$ .

הוכחה:

∎

תרגיל

הוכיחו/הפריכו את הטענה הבאה:

u \in L_{1} \land v \in L_{2} \iff u \circ v \in L_{1} \circ L_{2}

הוכחה:
⇒: נכון לפי הגדרת $L_{1} \circ L_{2}$ .
⇐: נסתכל על דוגמה נגדית:

L_{1}=\left\{ aab \right\},\; L_{2}=\left\{ bba \right\}

u=a,v=abbba

∎

7 - אוטומט סופי דטרמיניסטי

מבוא לתורת הקבוצות ואוטומטים למדמח

אוטומט סופי דטרמיניסטי

7 - אוטומט סופי דטרמיניסטי

מבוא לתורת הקבוצות ואוטומטים למדמח

אוטומט סופי דטרמיניסטי

תרגול

תרגול