הקדמה - מהי בעיה חישובית

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

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

אוסף פקודות(פעולות אריתמטיות , לולאות, תנאים והשמות).
זכרון שעומד לרשותנו.

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

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

הגדרה (בעיית הכרעה)

נקרא לבעיה בעיית הכרעה כאשר הקלט שלה הוא רצף ביטים והפלט שלה הוא ביט יחיד.

שפות ומילים

הגדרה 1 (א"ב)

א"ב הוא קבוצה סופית ולא ריקה של אותיות, כאשר אותיות הן פשוט סימנים.

\Sigma_{1}=\left\{ 0,1 \right\}

\Sigma_{2}=\left\{ 0,1,\dots,9 \right\}

\Sigma_{3}=\left\{ a,b,c \right\}

הגדרה 2 (מילה)

מילה מעל א"ב $\Sigma$ היא רצף סופי של אותיות מתוך $\Sigma$ .

0110 היא מילה מעל $\Sigma_{1}$ (וגם מעל $\Sigma_{2}$ )
המילה ababbc היא מעל $\Sigma_{3}$ .

באופן פורמלי, ניתן לכתוב כי 0110 זו בעצם הרביעיה הסדורה $(0,1,1,0)\in\Sigma_{1}^4$ .

הגדרה 3 (המילה הריקה)

מעל כל א"ב מוגדרת המילה הריקה שהיא רצף באורך 0. נסמנו $\epsilon$ .

דוגמה

האורך של $abba$ הוא 4 ( $|abba|=4$ ).
האורך של $b$ הוא 1.
האורך של $\epsilon$ הוא 0.

הגדרה 4 (שפה)

שפה מעל $\Sigma$ היא קבוצת מילים מעל $\Sigma$ .

דוגמה

L_{1}=\left\{ 0,00,001 \right\}

$L_{1}$ היא שפה מעל $\Sigma_{1}$ או $\Sigma_{2}$ .

L_{2}=\left\{ w|\Sigma_{2}\R{\text{ מעל }}w\R{\text{ זוגי, }}|w| \right\}

נראה כמה איברים: $L_{2}=\left\{ \epsilon ,00,01,02,03,\dots \right\}$ - היא $\infty$ -ית..

L_{3}=\emptyset

השפה הריקה מעל כל א"ב.

L_{4}=\left\{ w|w \in \Sigma_{3} \right\}

L_{4}=\left\{ \epsilon,a,b,c,aa,ab,\dots \right\}

הערה

נסמן שפה שבה יש את כל המילים מא"ב מסויים כ- $\Sigma^*$ .

הערה

$\epsilon$ יכולה להיות שייכת או לא שייכת לשפה מסויימת.
נראה כי $\epsilon \not\in L_{1},\epsilon \not\in L_{3},\epsilon \in L_{2},L_{4}$ .

פעולות על מילים ושפות

שרשור מילים

הגדרה 5 (שרשור מילים)

עבור $u=\sigma_{1}\dots\sigma_{k}$ ו- $v=\sigma_{1}'\dots\sigma_{m}'$ השרשור שלהן הוא:

u \cdot v=\sigma_{1}\dots\sigma_{k}\sigma_{1}'\dots\sigma_{m}'

הערה

נשים לב כי הפעולה אינה קומוטטיבית, שכן:

aba \cdot bc =ababc

bc \cdot aba = bcaba

נשים לב גם כי האדיש השרשורי הינו המילה הריקה - $\epsilon$ .

חזקה של מילים

הגדרה 6 (חזקה של מילים)

עבור מילה $w$ נאמר כי:

w^i=\underbracket{w\cdot w\cdot\ \dots\ \cdot w}_{\R{\text{ פעמים }}i}

פורמלית נכתוב כי לכל $w \in\Sigma^*$ מתקיים $w^0=\epsilon$ ו-

\forall i \in \mathbb{N}^+:\; w^{i}=w^{i-1} \cdot w

דוגמה

(ab)^3=(ab)^2ab=ababab

שרשור שפות

הגדרה 7 (שרשור שפות)

יהיו $L_{1},L_{2}$ שפות מעל $\Sigma$ .

L_{1}\cdot L_{2}=\left\{ u \cdot v|u \in L_{1} \land v \in L_{2} \right\}

דוגמה

\left\{ a,ab \right\}\cdot \left\{ bbc,\epsilon,a \right\}=\left\{ abbc,a,aa,abbc,ab,aba \right\}

הערה

לכל שפה $L$ מתקיים:

L \cdot \emptyset = \emptyset

ונראה כי:

L\cdot \left\{ \epsilon \right\}=L

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

חזקה של שפות

הגדרה 8 (חזקה של שפות)

לכל שפה $L$ מעל א"ב $\Sigma$ מתקיים:

L^0=\left\{ \epsilon \right\} \qquad \forall i \in \mathbb{N}^+:\; L^i=L^{i-1}\cdot L

כלומר: $L^i=\underbracket{L\cdot L\cdot\ \dots\ \cdot L}_{i}$

דוגמה

\left\{ a,bb \right\}^2=\left\{ abb,aa,bbbb,bba \right\}

אוטומטים

אוטומט סופי

דטרמיניסטי

נניח ונרצה לכתוב תוכנית שקלט שלה הוא מערך מעל $\Sigma=\left\{ a,b \right\}$ והיא מחזירה TRUE ⇔ מספר אותיות $a$ הוא אי-זוגי.
איך נעשה זאת?

נקצה מונה $c$ מאותחל ל-0
נסרוק את המערך משמאל לימין. בכל מעבר על $a$ נבצע $c++$ .
נחזיר $c\%2$ .

נשים לב כי אנו לא באמת זקוקים למונה, אלא רק למשתנה בוליאני שיגיד לנו אם מספר ה- $a$ -ים הוא זוגי או לא. בכל איטרציה, אם נקבל $a$ נבצע $t=!t$ .
נשים לב כי התוכנית הזו מאוד פשוטה ונוכל לצייר את אופן הפעולה שלה כך:

כאשר אנו מגיעים לעיגול כפול בסוף התוכנית, אזי נקבל $true$ , אחרת, נקבל $false$ - נקרא למצב זה מצב מקבל.

הגדרה (הגדרה לא פורמלית לאוטומט סופי דטרמיניסטי)

אוטומט סופי דטרמיניסטי מייצג תוכנית פשוטה שהקלט שלה הוא מילה מעל $\Sigma$ .
הריצה שלה מתחילה במצב התחלתי, קוראת את המילה אות לאחר אות ומתקדמת בהתאם במעברים.
הפלט שלה בסוף הקריאה הוא $true/false$ בהתאם לסוג המצב(מקבל/לא מקבל - דוחה) שבו היא נמצאת.

הגדרה 9 (אוטומט סופי דטרמיניסיטי - DFA)

תהי קבוצת מצבים $Q\neq \emptyset$ וסופית, כאשר בה קיים מצב התחלתי $q_{0}\in Q$ . תהי גם את קבוצת המצבים המקבלים: $F \subseteq Q$ .
נגדיר פונקציה $\delta:Q\times\Sigma\to Q$ אשר מספר לנו לאן לעבור בכל מצב ועם כל אות.
נגדיר את האוטומט הסופי הדטמיניסיטי $A$ להיות:

A=(Q,\Sigma,q_{0},\delta,F)

כעת נרצה לתאר כיצד האוטומט עובד.

הגדרה 10 (ריצה של אוטומט על מילה)

ריצה של $A$ מעל $w=\sigma_{1}\sigma_{2}\dots\sigma_{k}$ מעל $\Sigma$ תהא סדרה מהצורה:

s_{0}\overset{\sigma_{1}}{\longrightarrow}s_{1}\overset{\sigma_{2}}{\longrightarrow}s_{2}\dots \overset{\sigma_{k}}{\longrightarrow}s_{k} \qquad s_{0}\dots s_{k}\in Q, s_{0}=q_{0}

ולכל $0\leq i<k$ מתקיים $\delta(s_{i},\sigma_{i+1})=s_{i+1}$ .

נניח בריצה של האוטומט שראינו ממקודם על aba:

t_{0}\overset{a}{\longrightarrow}t_{1}\overset{b}{\longrightarrow}t_{1}\overset{a}{\longrightarrow}t_{0}

הגדרה 11 (ריצה מקבלת)

ריצה נקראת מקבלת אם $s_{k}\in F$ , אחרת, תקרא דוחה.
נניח למילה $w$ והאוטומט $A$ נגיד ש- $A$ מקבלת את $w$ או ש- $A$ דוחה את $w$ .

דוגמה

בריצה על המילה $aba$ נגיד כי $A$ דוחה את $aba$ אך $A$ מקבלת את $aaa$ .

הגדרה 12 (שפה של אוטומט)

השפה של $A$ היא קבוצת כל המילים ש- $A$ מקבל.

דוגמה

בדוגמה שלנו:

L(A)=\left\{ w \in \left\{ a,b \right\}^*|\#_{a}(w)\bmod 2=0 \right\}

כאשר $\#_{a}(w)$ הוא מספר מופעי $a$ במילה $w$ .

פונקציית המעברים המורחבת

הגדרה 13 (הפונקציה

\delta

מעל מילים)

נרחיב את $\delta$ כך שתספר לכל מצב( $q$ ) ולכל מילה, לאיזה מצב האוטמט יגיע בקריאת המילה מ- $q$ .
לכל $w \in \Sigma^*$ ולכל מצב $q$ :

\delta^*(q,\epsilon)=q

לכל מילה מהצורה $w=u\sigma$ כאשר $u$ היא מילה ו- $\sigma$ היא אות, נגדיר:

\delta^*(q,u\sigma)=\delta(\delta^*(q,u),\sigma )

דוגמה

\delta^*(t_{1},ab)=\delta(\delta^*(t_{1},a),b)=\delta(\delta(\delta^*(t_{1},\epsilon),a),b)=\delta(\delta(t_{1},a),b)=\delta(t_{0},b)=t_{0}

למה (השרשור)

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

רעיון ההוכחה: נובע באינדוקציה מהגדרת פונקצית המעברים המורחבת.

שפות רגולריות

הגדרה 14 (השפה של האוטומט)

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

הגדרה 15 (שפה רגולרית)

שפה מעל $\Sigma$ נקראת רגולרית אם קיים $DFA\; A$ כך ש- $L(A)=L$ .
כלומר, אפשר לבנות $DFA$ ש- $L$ היא שפתו.

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

טענה

יהי $\Sigma$ א"ב.
$\Sigma^*$ רגולרית.

הוכחה:
נציג DFA $A_{1}$ כך ש- $L(A_{1})=\Sigma^*$ .

כעת, נוכיח כי השפה של האוטומט היא $\Sigma^*$ .
לכל $w \in\Sigma^*$ : $\delta^*(q_{0},w)=q_{0}$ כי $q_{0}$ הוא המצב היחיד באוטומט.

w \in \Sigma^* \iff \delta^*(q_{0},w) = q_{0} \iff w \in L(A_{1})

לכן, מתקיימת הכלה דו כיוונית בין השפה של האוטומט ל- $\Sigma^*$ ולכן, זוהי השפה של האוטומט.
∎

טענה

יהי $\Sigma$ א"ב.
$\emptyset$ רגולרית.

הוכחה:
נציג DFA $A_{2}$ כך ש- $L(A_{2})=\emptyset$ .

נראה כי:
לכל $w \in\Sigma^*$ : $\delta^*(q_{0},w)=w_{0}$ . $q_{0}$ דוחה, ולכן לכל $w \in \Sigma^*$ מתקיים $w \not\in L(A_{2})$ . ⇐ $L(A_{2})=\emptyset$ .
∎

הגדרה 16 (רישא)

רישא של $w$ היא מילה $x$ כך שקיימת מילה $y$ כך ש- $x \circ y=w$ .

דוגמה

נחמן.
רישות:
$\qquad$ א. נ
$\qquad$ ב. נח
$\qquad$ ג. נחמ
$\qquad$ ד. נחמן
$\qquad$ ה. $\epsilon$

טענה

יהי $\Sigma$ א"ב.
תהי $w=\sigma_{1}\sigma_{2}\dots\sigma_{n}$ מילה מעל $\Sigma$ . אז $\left\{ w \right\}$ רגולרית.

דוגמה

$\left\{ abb \right\}$ רגולרית.

הערה

נקרא ל- $q_{4}$ בור דוחה.
קיים גם בור מקבל אשר מרגע שמגיעים אליו, לא משנה מה מכניסים המילה מתקבלת.

הוכחה:
עבור $w$ כללית:

A_{w}=(\left\{ q_{0},\dots,q_{n} \right\}\cup \left\{ q_{\perp} \right\},q_{0},\delta,\left\{ q_{n} \right\})

כאשר לכל $q_{i}$ , $0\leq i\leq n$ מתקיים:

\delta(q_{i},\sigma_{i+1})=q_{i+1}

ולכל $\sigma=\sigma_{i+1}$ מתקיים:

\delta(q_{i},\sigma)=q_{\perp}

לכל $\sigma \in\Sigma$ :

\delta(q_{n},\sigma)=\delta(q_{\perp},\sigma)=q_{\perp}

הוכחת נכונות הבנייה:

שיעורי בית (HW)

נסו להוכיח באינדוקציה את שני הסעיפים הבאים.
הוכחה חסרה פה!

לכן, לכל $u \in\Sigma^*$ :

אם $u$ היא הרישא באורך $i$ של $w$ : $\delta^*(q_{0},u)=q_{i}$ .
אם $u$ אינה רישא של $w$ : $\delta^*(q_{0},u)=q_{\perp}$

לכן, המילה היחידה שמגיעה ל- $q_{n}$ היא $w$ , שכן היא רישא באורך $n$ של $w$ .
מכיוון ש- $q_{n}$ הוא המצב המקבל היחיד:

L(A_{w})=\left\{ w \right\}

∎

תכונות של שפות רגולריות

1. סגירות תחת השלמה.

הגדרה 17 (המשלים לשפה)

המשלים לשפה היא קבוצת כל המילים שלא נמצאים בשפה:

\overline{L}=\Sigma^* \setminus L

משפט

שפות רגולריות סגורות תחת השלמה.

רעיון ההוכחה:
נחליף בין המצבים המקבלים לדוחים ב-DFA עבור $L$ .

הוכחה:
השפה $L$ רגולרית ולכן קיים DFA $A$ כך ש- $L(A)=L$ .

A=(Q,\Sigma,q_{0},\delta,F)

נגדיר:

A'=(Q,\Sigma,q_{0},\delta,\underbracket{Q \setminus F}_{F'})

נראה כי $L(A')=\overline{L}$ .

w \in L(A') \underset{\begin{matrix} \downarrow \\ DFA\R{\text{הגדרת }} \end{matrix}}{\iff} \delta^*(q_{0},w) \in Q' \iff \delta^*(q_{0},w) \in Q \setminus F\underset{\begin{matrix} \downarrow \\ A'\R{\text{הגדרת }} \end{matrix}}{\iff} w \not\in L(A)

ולכן, $L(A')=\overline{L(A)}=\overline{L}$ .
∎

2. סגירות תחת חיתוך

משפט

חיתוך של שתי שפות רגולריות סגורה תחת חיתוך.

דוגמה

כעת, נבנה את האוטומט $A$ :

נוכיח כי אם $L_{1},L_{2}$ רגולריות, אזי $L_{1} \cap L_{2}$ רגולרית.
הוכחה:
יהיו:

A_{1}=(Q,\Sigma,q_{0},\delta_{1},F_{1})

A_{2}=(P,\Sigma,p_{0},\delta_{2},F_{2})

כעת, נגדיר אוטומט סופי דטרמיניסטי $A$ :

A=(Q \times P,\Sigma,(q_{0},p_{0}),\delta,F_{1}\times F_{2})

ונגדיר: לכל $q \in Q,p \in P,\sigma \in \Sigma$ :

\delta((q,p),\sigma)=(\underbracket{\delta_{1}(q,\sigma)}_{q'},\underbracket{\delta_{2}(p,\sigma)}_{p'})

הוכחת נכונות:

טענה (טענת עזר)

לכל $(q,p)$ ולכל $w \in \Sigma^*$ :

\delta^*((q,p),w)=(\underbracket{\delta_{1}^*(q,w)}_{q'},\underbracket{\delta_{2}^*(p,w)}_{p'})

נוכיח זאת באמצעות אינדוקציה על $w$ :

בסיס: $w=\epsilon$ .

\delta^*((q,p),\epsilon)=(q,p)=(\delta_{1}^*(q,\epsilon),\delta_{2}^*(p,\epsilon))

צעד:

נניח כי הטענה נכונה עבור $w$ ונוכיח כי זה מתקיים עבור $w\sigma$ כאשר $\sigma \in\Sigma$ .

\delta^*((q,p),w\sigma)=\delta(\delta^*((q,p),w),\sigma)=\delta((\delta_{1}^*(q,w),\delta_{2}^*(p,w)), \sigma)

=(\underbracket{\delta_{1}(\delta_{1}^*(q,w),\sigma)}_{q''},\underbracket{\delta_{2}(\delta_{2}^*(p,w),\sigma)}_{p''})=(\delta_{1}^*(q,w\sigma),\delta_{2}^*(p,w\sigma))

כעת, לאחר שהוכחנו את טענת העזר, נחזור להוכחת המשפט:

w \in L(A) \iff \delta^*((q_{0},p_{0}),w) \in F_{1} \times F_{2}

\underset{\begin{matrix} \downarrow \\ \R{\text{טענת העזר}} \end{matrix}}{\iff} (\delta_{1}^*(q_{0},w),\delta_{2}^*(p_{0},w)) \in F_{1} \times F_{2} \iff \delta_{1}^*(q_{0},w) \in F_{1} \land \delta_{2}^*(p_{0},w) \in F_{2}

\iff w \in L_{1} \land w \in L_{2} \iff w \in L_{1} \cap L_{2}

∎

מסקנה

מכיוון ששפות רגולריות סגורות תחת משלים וחיתוך, אזי לפי דה-מורגן, הן סגורות תחת איחוד.

L_{1} \cup L_{2}=\overline{\overline{L_{1}} \cap \overline{L_{2}}}

3. סגירות תחת איחוד

במקום כללי דה-מורגן, ניתן להשתמש במבנה המכפלה ולהגדיר את קבוצת המצבים המקבלים כך:

(F_{1}\times P)\cup(Q \times F_{2})

משפט

שפות רגולריות סגורות תחת פעולות בסיסיות על קבוצות.

3.1 איחוד סופי

משפט

שפות רגולריות סגורות תחת איחוד סופי.
יהיו $L_{1},\dots,L_{n}$ רגולריות. אזי $\bigcup_{1\leq i\leq n}L_{i}$ רגולרית.

רעיון ההוכחה:
באינדוקציה פשוטה עם כלל התחלה $i=0$ : האיחוד הוא $\emptyset$ : שפה רגולרית. הצעד נובע מיידית מסגירות לאיחוד.

הערה

שפות רגולריות לא סגורות תחת איחוד $\infty$ .
כלומר, קיימת סדרה $\infty$ של שפות רגולריות, כך שהאיחוד האינסופי שלהן( $\bigcup_{i\geq1}L_{i}$ ) לא רגולרית.

שפות לא רגולריות

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

L_{ab}=\left\{ a^ib^i|i \in \mathbb{N} \right\}

L_{ab}=\left\{ \epsilon,ab,aabb,aaabbb,\dots \right\}

נוכיח כי $L_{ab}$ אינה רגולרית. כלומר, לא קיים אוטומט סופי דטרמיניסטי כך ש- $L(A)=L_{ab}$ .
הוכחה:
נניח בשלילה כי קיים אוטומט סופי דטרמיניסטי $A$ .

A=(Q,\left\{ a,b \right\},q_{0},\delta,F)

כך ש- $L(A)=L_{ab}$ . נסמן $|Q|=n$ .
נתבונן בקבוצת המילים: $S=\left\{ a,a^2,a^3,\dots,a^{n+1} \right\}$ . מעקרון שובך היונים(לא - היא לא הגדירה את זה קודם), קיימות שתי מילים $a^i,a^j \in S$ כאשר $i<j$ כך ש:

\delta^*(q_{0},a^i)=\delta^*(q_{0},a^j)\underset{\R{\text{סימון}}}{=}q

נתבונן ב- $\delta^*(q,b^i)=p$ . באמצעות למת השרשור, נדע כי מתקיים: $\delta^*(q_{0},a^ib^i)=\delta^*(q_{0},a^jb^i)=p$ .
האם $p \in F$ ?

אם לא, אז $\delta^*(q_{0},a^ib^i)\not\in F$ ולכן $a^ib^i \not\in L(A)$ - סתירה.
אם כן, אז $\delta^*(q_{0},a^jb^i)\in F$ ולכן $a^jb^i \in L(A)$ - סתירה.
∎

הערה

נראה אי-סגירות לאיחוד אינסופי:

L_{ab}=\bigcup_{i\geq 0}\underbracket{\left\{ a^ib^i \right\}}_{\R{\text{רגולרית}}}=\left\{ \epsilon \right\}\cup \left\{ ab \right\}\cup\left\{ aabb \right\}\dots

הערה

כל שפה סופית היא רגולרית, שכן היא איחוד סופי של יחידונים.

מסקנה

כל שפה לא רגולרית היא אינסופית. אך לא כל שפה אינסופית היא לא רגולרית.

שיטות להוכחת רגולריות או אי-רגולריות של שפות

למת הניפוח לשפות רגולריות

נראה תכונה שקיימת לכל שפה רגולרית, ולכן אם $L$ לא מקיימת אותה, אזי $L$ לא רגולרית.

תהי $L$ שפה רגולרית ויהי $A$ אוטומט סופי דטרמיניסטי עבור $L$ עם $n$ מצבים. נניח כי קיימת $w \in L$ כך ש- $|w|\geq n$ .

w=\sigma_{1}\sigma_{2}\dots\sigma_{m}\qquad m\geq n

נתבונן בריצה של $A$ על $w$ :

S_{0}\xrightarrow{\sigma_{1}}S_{1}\xrightarrow{\sigma_{2}}\dots \xrightarrow{\sigma _{n}}S_{n}\xrightarrow{\sigma_{n+1}}\dots \xrightarrow{\sigma_{m}}S_{m}

מספר המצבים בסדרה $(m+1=)n<$ . למעשה, כבר אחרי קריאת הרישא $\sigma_{1}\dots\sigma_{n}$ עוברים ב- $n+1$ מצבים.
לפי עקרון שובך היונים, קיימים $0\leq i<j\leq n$ כך ש- $S_{i}=S_{j}=q$ . נתבונן במסלול הריצה על $A$ כאשר נסמן $w=xyz$ .
[ציור]
מכיוון ש: $\delta^*(q,y)=q$ מתקיים כי לכל $i \in \mathbb{N}$ : $xy^iz \in L$ .
כלומר, ברגע שקיימת מילה ארוכה מספיק ב- $L$ , אפשר לחלק אותה ל-3 חלקים כך שישנן $\infty$ מילים שגם הן ב- $L$ שנוצרות ע"י "ניפוח" החלק האמצעי.

למה (הניפוח)

תהי $L$ שפה רגולרית. אזי קיים $n \in \mathbb{N}^+$ כך שלכל מילה $w \in L$ כך ש- $|w|\geq n$ קיים פירוק $w=xyz$ כך ש: $|xy|\leq n$ , $y\neq\epsilon$ ולכל $i\geq0$ מתקיים $xy^iz \in L$ .

הוכחה:
אם $L$ סופית, אזי עבור $<n$ אורך מילה מקסימלית ב- $L$ , התנאי מתקיים באופן ריק.
אחרת, $n$ הוא מספר המצבים באוטומט סופי דטרמיניסטי עבור השפה $L$ , והנכונות נובעת מהדיון הנ"ל.
∎

מסקנה

אם $L$ לא מקיימת את תנאי למת הניפוח, אזי היא אינה רגולרית.

איך נדע כי שפה לא מקיימת את התנאים? כעת, ננסח במדוייק.

משפט (שלילת הלמה)

לכל $n\geq1$ קיימת $w \in L$ , $|w|\geq n$ כך שלכל פירוק של $w$ : $w=xyz$ , כך ש- $y\neq \epsilon,|xy|\leq n$ קיים $i\geq 0$ כך ש: $xy^iz \not\in L$ .

דוגמה (לשימוש בלמת הניפוח כדי להוכיח ששפה אינה רגולרית)

$L_{ab}=\left\{ a^ib^i|i\geq n \right\}$ . הוכחה:
יהי $n\geq1$ . נבחר $w=a^nb^n$ . $w \in L,|w|\geq n$ ולכן היא כבילה.
נעבור על כל הפירוקים החוקיים של $w$ . נבחר את $x$ להיות רצף של $a$ -ים, את $y$ להיות רצף של $a$ -ים ואת $z$ להיות רצף של $a$ -ים ואז $b$ -ים.
לכן, $|xy|=n$ . כל הפירוקים של $w$ לפי תנאי הלמה הם מהצורה הבאה $w=\underbracket{a^s}_{x}\ \underbracket{a^t}_{y}\ \underbracket{a^{n-s-t}b^n}_{z}$ .
לכל $s,t$ כך ש- $t\neq0$ , $s+t\leq n$ קיים פירוק שונה.
לכל פירוק שכזה נבחר $i=2$ . $xy^2z=a^sa^ta^ta^{n-s-t}b^n$ שזה בעצם $xy^2z=a^{n+t}b^n$ . מכיוון ש- $t>0$ אזי $a^{n+t}b^n \not\in L$ .

הראנו כי $L_{ab}$ לא עומדת בתנאי הלמה, ולכן אינה רגולרית.
∎

הערה (מה מותר ומה אסור לבחור בהוכחה שכזו?)

\begin{array}{|c|c|} \hline \R{\text{לא בוחרים}} & \R{\text{בוחרים}} \\ \hline n & (\R{\text{שאורכה תלוי ב-n}}) w \\ \\ \R{\text{פירוק}} & (\R{\text{כתלות בפירוק}})i \\ \hline \end{array}

דוגמה

נסתכל על $\Sigma=\left\{ a \right\}$ ו- $L_{p}=\left\{ a^p | \R{\text{ ראשוני }} p \right\}$ . נוכיח כי $L_{p}$ לא רגולרית.
הוכחה: נוכיח בעזרת למת הניפוח.
יהי $n\geq1$ . נבחר ראשוני $p\geq n$ (יש כזה כי ישנם $\infty$ ראשוניים) ואת המילה $w_{p}=a^p$ .
כל הפירוקים של $a^p$ הם מהצורה: $a^sa^ta^{p-s-t}$ כך ש: $s+t\leq n$ ו- $t>0$ .
אנו כעת נחפש $i$ כך ש: $a^s(a^t)^ia^{p-s-t}$ מילה מאורך פריק.

a^sa^{it}a^{p-s-t}=a^{p+it-t}=a^{p+t(i-1)}

נבחר $i=p+1$ ואז נקבל כי $a^sa^{it}a^{p-s-t}=a^{p+t(p+1)}=a^{p(1+t)}$ ולכן מכיוון ש- $t+1>1,p>1$ ומכיוון שכפולה של שני מספרים הגדולים מ- $1$ היא אינה מספר ראשוני, אזי נקבל $a$ בחזקת מספר שאינו ראשוני ולכן היא לא נמצאת בשפה.

הראנו כי $L_{p}$ לא מקיימת את תנאי הלמה, ולכן אינה רגולרית.
∎

דוגמה ("הדוגמה החביבה של הסמסטר" - שרי)

שפת הפולינדורמים מעל $\left\{ a,b \right\}$ . (פולינדרום: מילה הנקראת באופן זהה בשני הכיוונים. דוגמה: $abba$ , אבא, אמא, $aibohphobia$ )
הוכחה:
יהי $n\geq1$ ונבחר(שווה להשקיע קצת זמן בבחירה טובה) את המילה $a^nba^n$ .
[המשיכו בבית]

דוגמה (לשפה שהיא לא רגולרית אבל כן ניתנת לניפוח)

זוהי דוגמה ללא הוכחה.

L=\left\{ a^ib^jc^k|j=k \R{\text{ אז }}i>0\R{\text{אם }} \right\}

נשים לב כי החלק הראשון הוא רגולרי וכן ניתן לניפוח. אך החלק השני הוא החלק הלא רגולרי.

משפט מייהיל-נרוד

המשפט נותן איפייון של שפות רגולריות שאינו בעזרת מודל חישובי, מאפשר למצוא אס"ד מינימלי (מבחינת מספר מצבים) לשפה רגולרית והוא כלי להוכחה ששפה אינה רגולרית.

יחס מייהיל-נרוד של שפה $L$

נניח כי $L$ רגולרית ויהי $A$ אס"ד עבור $L$ . יהיו $u,v$ שתי מילים כך ש: $q=\delta^*(q_{0},u)=\delta^*(q_{0},v)$ .
2 - אוטומטים 2026-01-18 10.41.36.excalidraw.svg
לכל $z \in\Sigma^*$ מתקיים כי $vz \in L \iff uz \in L$ .

הגדרה 18 (יחס מייהיל-נרוד)

תהי $L$ שפה. יחס מייהיל-נרוד של $L$ היא יחס מעל $\Sigma^*$ המוגדר:

vz \in L \iff uz \in L \quad :z \in \Sigma^* \R{\text{לכל }} \iff u \underset{_{L}}{\sim} v

דוגמה

\Sigma=\left\{ a,b \right\} \qquad L=\left\{ w | \R{\text{יש ב-w את ba}} \right\}

נתבונן ב- $a,ab$ . עבור $z=\epsilon$ מתקיים: $a \cdot \epsilon \not\in L$ וגם $ab \cdot \epsilon \in L$ ולכן, $\epsilon$ הוא זנב מפריד שמוכיח שהמילים אינן ביחס $\underset{_{L}}{\sim}$ . כלומר: $a \not \underset{_{L}}{\sim}ab$ .
נתבונן ב- $a,aa$ . שני אלו כן ביחס מייהיל-נרוד ונראה כמה אפשרויות: אם נשרשר מילים שיש בהן רק $a$ אז המילים לא יהיו בשפה ואם נשרשר מילה כלשהי שיש בה $b$ אז שתי המילים כן יהיו בשפה.
לכל $z$ , אם ב- $z$ אין $b$ מתקיים $az,aaz \not\in L$ ואחרת: $az,aaz \in L$ . ולכן $a \underset{_{L}}{\sim}aa$ .
נתבונן ב: $\epsilon,a$ . הם לא ביחס אחד עם השני. נראה כי $\begin{matrix}\epsilon \cdot b \not\in L \\ a \cdot b \in L\end{matrix}$ $\impliedby$ $\epsilon \not \underset{_{L}}{\sim} a$ .

טענה

לכל $L$ מעל $\Sigma$ , $\underset{_{L}}{\sim}$ הוא יחס שקילות מעל $\Sigma^*$ .

הוכחה:

רפלקסיבי: לכל $u \in\Sigma^*$ ולכל $z \in\Sigma^*$ מתקיים $uz \in L \iff uz \in L$ .
סימטרי: לכל $u,v \in\Sigma^*$ , אם $u \underset{_L}{\sim}v$ אז לכל $z$ :
$vz \in L \iff uz \in L \iff uz \in L \iff vz \in L \iff v \underset{_{L}}{\sim} u$
טרנזיטיבי: לכל $u,v,w \in\Sigma^*$ אם לכל $z$ מתקיים $vz \in L \iff uz \in L$ וכן מתקיים $wz \in L \iff vz \in L$ אז לכל $z$ מתקיים:
$wz \in L \iff uz \in L$
∎

היחס $\underset{_{L}}{\sim}$ מחלק את $\Sigma^*$ למחלקות שקילות. נבחין כי אם $u \in L$ ו- $v \notin L$ אז $u \underset{_{L}}{\sim}v$ כי $\epsilon$ מפרידה ביניהן.

מסקנה

לכל מחלקת שקילות $S$ או $S \subseteq L$ או $S \subseteq \overline{L}$ .

המשפט

טענה

אם $L$ רגולרית, אז מספר מחלקות השקילות של $\underset{_{L}}{\sim}$ הוא סופי.
נסמן: $Rank(\underset{_{L}}{\sim})$ .

הוכחה:
תהי $L$ רגולרית מעל $\Sigma$ ויהי $A$ אס"ד עבור $L$ . יהי $q$ מצב ב- $A$ .
ראינו כי לכל $u,v$ שמגיעות ל- $q$ , לכל $z$ : $vz \in L \iff uz \in L$ ולכן $u \underset{_{L}}{\sim}v$ . לכן, כל המילים שמגיעות לאותו המצב הן באותה מחלקת שקילות.
נסמן ב- $L_{q}$ את קבוצת המילים שמגיעות ל- $q$ . אז קיימת מחלקת שקילות $S$ של $\underset{_{L}}{\sim}$ כך ש- $L_{q}\subseteq S$ .
לכן, מספר המצבים ב- $Rank(\underset{_{L}}{\sim})\leq A$ . (המצבים באוטומט מחלקים את $\Sigma^*$ : כל מילה מגיעה למצב יחיד) $\impliedby$ $Rank(\underset{_{L}}{\sim})$ סופי.
∎

משפט (מייהיל-נרוד)

\R{\text{ סופי}} Rank(\underset{_{L}}{\sim}) \iff \R{\text{ רגולרית}} L

הוכחה:
⇐: הוכחנו כעת.
⇒: תהי $L$ עבורה $Rank(\underset{_{L}}{\sim})$ סופי: $S_{1},S_{2},\dots,S_{k}$ . נבנה $DFA$ שבו המצבים הם $S_{1},\dots,S_{k}$ וכל מילה $u$ מגיעה ל- $[u]$ :

A=(\left\{ S_{1},\dots,S_{k} \right\}, \Sigma,[\epsilon],\delta,\left\{ S| S \subseteq L \right\})

לכל $[w]$ ולכל $\sigma$ :

\delta([w],\sigma)=[w\sigma]

נראה כי $\delta$ הינה פונקציה ואינה תלויה בנציג. נניח בשלילה שקיימות $u,v$ כך ש: $[u]=[v]$ אך $[u\sigma]\neq[v\sigma]$ .
אם $u\sigma \underset{_{L}}{\sim}v\sigma$ קיים $z$ מפריד כך ש- $u\sigma z \in L$ וגם $v\sigma z \not\in L$ (או להפך) אבל אז $\sigma z$ מפריד בין $u,v$ בסתירה לכך ש- $u \underset{_{L}}{\sim}v$ .
לכן, $A$ הוא אוטומט סופי דטרמיניסטי.

טענה (טענת עזר)

לכל $w \in\Sigma^*$ מתקיים $\delta^*([\epsilon],w)=[w]$

הוכחה: באינדוקציה על $w$ . (לבד!!!)

וכעת, $\R{\text{ מקבל}}\delta^* \iff w \in L(A)$ ולכן, לפי טענת העזר:

w \in L(A) \iff \R{\text{ מקבל}} [w] \iff [w] \subseteq L \iff w \in L

∎

הערה

נשים כי האוטומט שבנינו הוא אס"ד מינימלי עבור $L$ כי $Rank(\underset{_{L}}{\sim})=|Q|$ .

משפט (הנוגד הלוגי למייהיל-נרוד)

\R{\text{ אינסופי}} Rank(\underset{_{L}}{\sim}) \iff \R{\text{ לא רגולרית}} L

כלומר, אם נוכיח של- $\underset{_{L}}{\sim}$ של- $L$ יש $\infty$ מחלקות שקילות $\impliedby$ היא לא רגולרית.

דוגמה

נוכיח שוב ש- $L_{ab}=\left\{ a^nb^n|b \in \mathbb{N} \right\}$ אינה רגולרית בעזרת מייהיל-נרוד.
נחפש קבוצה אינסופית של מילים שכל אחת מהן במחלקת שקילות שונה. כלומר, נראה שבין כל שתיים מהן יש זנב מפריד.
נבחר: $T=\left\{ a^i|i \in \mathbb{N} \right\}$ . נראה שבין כל שתיים מהמילים ב- $T$ יש מילה מפרידה: יהיו $a^j,a^{j'}$ שתי מילים שונות מ- $T$ . $b^j$ היא מילה מפרידה שכן:

a^jb^j \in L \land a^{j'}b^j \notin L

ולכן, לא קיימות שתמי מילים ב- $T$ באותה מחלקת שקילות ולכן, כל מילה ב- $T$ שייכת למחלקת שקילות שונה ולכן $T$ אינסופית ולכן ישנן $\infty$ מחלקות שקילות ולכן, לפי מייהיל-נרוד השפה $L_{ab}$ אינה רגולרית.

דגשים

הקבוצה $T$ חייבת להיות $\infty$ .
הקבוצה $T$ לא חייבת להיות מוכלת ב- $L$ או ב- $\overline{L}$ .
ההוכחה עבור $T$ חייבת להיות כללית. כלומר, לכל שתי מילים מ- $T$ .

אי-דטרמיניסטי

באוטומט סופי דטרמיניסטי יש מצב התחלתי יחיד והמעברים הם פונקציה. כלומר, לכל מצב + אות יש מצב יעד יחיד.
באוטומט סופי לא דטרמיניסטי ישנה קבוצת מצבים התחלתיים והמעברים הם יחס עם איברים מהצורה $(q,\sigma,p)$ .

דבר זה נראה מעט מוזר שכן לא ברור לאן אנו הולכים מכל אות, שכן יש לנו כמה דרכים שאנו יכולים ללכת בהן.

דוגמה

נשים לב למשהו מעניין פה - באוטומט זה ישנן ריצות שונות על מילים כגון $w=aa$ :

\begin{matrix} q_{0}\xrightarrow{a}q_{0}\xrightarrow{a}q_{0} \\ q_{0}\xrightarrow{a}q_{0}\xrightarrow{a}q_{1} \\ q_{0}\xrightarrow{a}q_{1}\xrightarrow{a}q_{2} \end{matrix}

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

הגדרה 19 (מילה מתקבלת באוטומט סופי לא דטרמיניסטי)

מילה $w$ מתקבלת ע"י אוטומט סופי אי דטרמיניסטי( $NFA$ ) אם קיימת ריצה מקבלת על $w$ .

בדוגמה שראינו, על המילה $w=ba$ כלל לא קיימת ריצה. ובפרט, לא קיימת ריצה מקבלת.

משפט

מילה $w$ לא מתקבלת באוטומט סופי אי דרטמיניסטי $A$ אם כל הריצות של $A$ על $w$ דוחות.

הערה

תנאי ה"לכל" יכול להתקיים באופו ריק. כלומר: אם אין ל- $A$ ריצה על $w$ , אזי $w$ לא מתקבלת.

הגדרה 20 (אוטומט סופי לא דטרמיניסטי)

יהי $A$ אוטומט סופי לא דרטמיניסטי.

A=(Q,\Sigma,I,R,F)

כאשר:

$Q$ היא קבוצת המצבים, כמו בדטרמיניסטי.
$\Sigma$ היא א"ב של האוטומט, בדיוק כמו בדטרמיניסטי.
$I$ היא קבוצת המצבים ההתחלתיים. $I \subseteq Q$
$R$ הוא יחס המעברים המוגדר: $R \subseteq Q\times\Sigma \times Q$
$F$ היא קבוצת המצבים הסופיים, כמו בדטרמיניסטי.

ריצה של אוטומט $A$ על $w=\sigma_{1}\dots\sigma_{n}$ היא סדרה:

\underbracket{S_{0}}_{\in\ I}\xrightarrow{\sigma_{1}}S_{1}\xrightarrow{\sigma_{2}}S_{2}\dots \xrightarrow{\sigma_{n}}S_{n}

כך ש- $S_{0} \in I$ ולכל $1\leq i\leq n$ : $(S_{i-1},\sigma_{i},S_{i})$ כמו בוגמות על $aa$ .
הריצה מקבלת אילו $S_{n}\in F$ .

נשים לב לבעיה - איך נוכל להגדיר איך נראת ריצה על מילה? באוטומט סופי דטרמיניסטי, מכיוון שהייתה לנו פונקציית מצבים $\delta$ , יכלנו להגדיר פונקציה מורחבת $\delta^*$ כך שהיא תהא ריצה על מילה שלמה. פה לא נוכל לעשות את זה כי $\delta$ לא קיימת. במקום זאת, יבוא לעזרתינו הסימון הבא:

משפט

נסמן $q \overunderset{w}{A}{\longrightarrow}p$ אם אפשר להגיע ל- $p$ בקריאה של $w$ מ- $q$ .

סימון זה הוא תחליף ל- $\delta^*$ .

הגדרה 21 (שפת אוטומט סופי לא דטרמיניסטי)

השפה של אוטומט סופי לא דרטמינסיטי $A$ היא:

L(A)=\left\{ w|\exists q_{0} \in I,\exists p \in F:]; q_{0}\overunderset{w}{A}{\longrightarrow}p \right\}

דוגמה

נזכר בדוגמה ממקודם ונמצא לאוטומט $A$ את השפה שלו.

נסתכל על כל האפשרויות שלנו ונייצג כל אחת מהן כקבוצה:

\underset{q_{1}\R{\text{מילים שלא עוברות דרך }}}{\left\{ a^ib^i|i\geq 0,j\geq 1 \right\}}\cup \underset{\R{\text{מילים שעברו ב-q}}}{\left\{ a^ib^i|i\geq 2,j\geq0 \right\}} \cup \underset{\R{\text{סוג שני של מילים שעברו ב-q}}}{\left\{ a^ib^i|i\geq 1,j\geq 1 \right\}}

נשים לב שהקבוצה השמאלית מוכלת בקבוצה הימנית ולכן נוכל לצמצם אותה בתיאור.
נבנה כעת $DFA$ עבור $L(A)$ :

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

משפט

לכל שפה רגולרית קיים אוטוטמט סופי לא דטרמיניסטי המתאר אותה.

הוכחה:
קל לראות שלכל שפה רגולרית $L$ קיים אוטומט סופי לא דטרמיניסטי $A$ כך ש- $L(A)=L$ . $L$ רגולרית ⇐ קיים אוטומט סופי דטרמיניסטי $B$ כך ש- $L(B)=L$ .

B=(Q,\Sigma,q_{0},\delta,F)

ונגדיר: $A=(Q,\Sigma,\left\{ q_{0} \right\},\delta,F)$ .
הריצה של $B$ על $w$ מקבלת $\iff$ $w \in L(B)$ $\impliedby$ קיימת ריצה מקבלת של $A$ על $w$ $\impliedby$ $w \in L(A)$ .
הריצה של $B$ על $w$ דוחה $\iff$ $w \not\in L(B)$ $\underset{\begin{matrix}\R{\text{קבוצת הריצות}}\\\R{\text{היא יחידון}}\end{matrix}}{\impliedby}$ כל הריצות של $A$ על $w$ דוחות $\impliedby$ $w \not\in L(A)$ .
∎

משפט

יהי $A$ אוטומט סופי לא דטרמיניסטי. אזי $L(A)$ רגולרית.

הוכחה:
יהי $A=(Q,\Sigma,I,R,F)$ אוטומט סופי לא דטרמיניסטי. נבנה אוטומט סופי דטרמיניסטי $D$ כך ש- $L(D)=L(A)$ .

הערה (ענן המחשבות שלנו)

נחזור לאוטומט המכפלה. היו לנו שם שני אוטומטים ורצינו לרוץ על שתי הריצות בו זמנית. לכך בנינו אוטומט המורכב משני מצבים.
נרצה להשתמש באותו הרעיון פה להוכחה זו.
2 - אוטומטים 2026-01-04 11.40.37.excalidraw.svg
$D$ יעקוב אחרי קבוצת המצבים שמגיעים אליהן כשמתקדמים על כל הריצות של $A$ על $w$ בו
כל מצב ב- $D$ ייצג קבוצת מצבים ב- $A$ ומצב ב- $D$ יהיה מקבל אם הוא מייצג קבוצה אשר קיים בה לפחות מצב מקבל אחד.

נגדיר:

D=(P(Q),\Sigma,I,\delta,\left\{ S \in P(Q)|S \cap F \neq \emptyset \right\})

כאשר $I \in P(Q)$ מצב יחיד וקבוצת המצבים המקבלים היא כל תת הקבוצות של $Q$ שיש בהן מצב מקבל של $A$ .
כעת, נותר לנו רק להגדיר את $\delta$ .

\forall \sigma \in\Sigma,\forall S \in P(Q):\; \delta(S,\sigma)=\left\{ \begin{array}{c|c} q & \exists q \in S:\; q \overunderset{\sigma}{A}{\longrightarrow}p \end{array} \right\}

כעת נוכיח את נכונות האוטומט.

טענה (טענת עזר)

\forall w \in\Sigma^*,\forall S \in P(Q):\; \delta^*(S,w)=\left\{ \begin{array}{c|c} p & \exists q \in S:\; q \overunderset{w}{A}{\longrightarrow}p \end{array} \right\}

הוכחה:
באינדוקציה על אורך $w$ .
בסיס: $w=\epsilon$ .

\delta^*(S,\epsilon)\underset{\delta}{=}S=\left\{ \begin{array}{c|c} p & \exists q \in S:\; q \overunderset{\epsilon}{A}{\longrightarrow}p\end{array} \right\}

צעד: נניח נכונות עבור $w$ באורך $n$ ונוכיח עבור $w\sigma$ לכל $\sigma \in\Sigma$ :

\delta^*(S,w\sigma)=\delta(\delta^*(S,w),\sigma)

לפי הנחת האינדוקציה, $\delta^*(S,w)=\left\{ \begin{array}{c|c}q'&\exists t \in S:\; t \overunderset{w}{A}{\longrightarrow}q'\end{array} \right\}$

=\left\{ \begin{array}{c|c} p & \exists t \in S,q \in Q:\; t \xrightarrow{w}q \xrightarrow{\sigma}p \end{array} \right\}=\left\{ \begin{array}{c|c} p & \exists t \in S;\; t \overunderset{w\sigma}{A}{\longrightarrow}p \end{array} \right\}

∎

w \in L(D) \iff \delta^*(I,w) \in \left\{ \begin{array}{c|c} S & S \cap F \neq \emptyset \end{array} \right\} \iff \left\{ \begin{array}{c|c} p & \exists q \in I:\; \overunderset{w}{A}{\longrightarrow}p \end{array} \right\} \in \left\{ \begin{array}{c|c} S & S \cap F \neq \emptyset \end{array} \right\}

\iff \left\{ \begin{array}{c|c} p & \exists q \in I: q \overunderset{w}{A}{\longrightarrow} p \end{array} \right\} \cap F \neq \emptyset \iff \exists q \in I, \exists p \in F:\; q \overunderset{w}{A}{\longrightarrow} p \iff w \in L(A)

∎

מסקנה

השפה $L$ רגולרית $\iff$ קיים אוטומט סופי לא דטרמינסיטי $A$ כך ש- $L(A)=A$ .

דוגמה

נסתכל על האוטומט $A$ ממקודם:

וכעת, נבנה לו אוטומט סופי דטרמיניסטי - $D$ :

ועוד שלושה מצבים שלא הגענו אליהם.

דוגמה (דוגמה לשפה עם

NFA

קטן ו-

DFA

גדול)

\Sigma_{n}=\left\{ 1,2,\dots,n \right\}

נגדיר: $L_{n}=\left\{ w \in \Sigma_{n}^* |w \R{\text{ שלא מופיעה ב-}}\Sigma_{n}\R{\text{קיימת אות מ-}} \right\}$
נראה אוטומט סופי לא דטרמיניסטי עבור $L_{n}$ :

שימושי $NFA$

בניות בעזרת $NFA$

ראינו כי בהינתן אוטומט סופי דטרמיניסטי $A_{1},A_{2}$ אפשר להסתמך על בניית המכפלה כדי לבנות אוטומט סופי דטרמיניסטי עבור $L(A_{1})\cup L(A_{2})$ .
אם ב- $A_{1}$ ישנם $n_{1}$ מצבים וב- $A_{2}$ ישנם $n_{2}$ מצבים, אזי, ב- $A$ ישנם $n_{1}\cdot n_{2}$ מצבים.
כעת, נניח כי יש לנו אוטומט סופי לא דטרמיניסטי $A_{1},A_{2}$ נבנה עבור $L(A_{1})\cup L(A_{2})$ :

A=(Q_{A_{1}}\cup Q_{A_{2}},\Sigma,I_{A_{1}}\cup I_{A_{2}},R_{A_{1}}\cup R_{A_{2}},F_{1}\cup F_{2})

נראה כי:

w \in L(A) \iff \R{\text{קיימת עליה ריצה מקבלת באחד מהם}} \iff w \in L(A_{1})\cup L(A_{2})

מספר המצבים: $n_{1}+n_{2}$ .

הוכחת סגירות רגולריות להיפוך

נגדיר $w^R=\sigma_{n}\sigma_{n-1}\dots\sigma_{1}$ כאשר $w=\sigma_{1}\dots\sigma_{n-1}\sigma_{n}$ .
עבור שפות, בהנתן שפה $L$ :

L^R=\left\{ w^R|w \in L \right\}

דוגמה

L=\left\{ \epsilon,ab,abb \right\} \implies L^R=\left\{ \epsilon,ba,bba \right\}

טענה

אם $L$ רגולרית, גם $L^R$ רגולרית.

סקיצת הוכחה:
נקח אוטומט סופי לא דטרמיניסטי עבור $L$ . נסמנו $A$ .
כעת, נבנה אוטומט עבור $L^R$ :

A'=(Q,\Sigma,F_{A},R',I_{A})

R'=\left\{ (p,\sigma,q)|(q,\sigma,p)\in R_{A} \right\}

שיעורי בית (HW)

השלימו את החסר

∎

מעברי $\epsilon$

הרעיון: מעברי $\epsilon$ מאפשרים להמשיך את הריצה ממצב אחר מבלי להתקדם על הקלט.

נראה ריצה לדוגמה:

\to q_{0}\xrightarrow{a}q_{1}\xrightarrow{b}q_{2}\xrightarrow{\epsilon}q_{0}\xrightarrow{a}q_{1}\xrightarrow{b}q_{2}\xrightarrow{\epsilon}q_{3}

זוהי ריצה מקבלת על המילה $abab$ .

הערה

לא חובה לעבור במעבר $\epsilon$ . אם יש מעבר $q \xrightarrow{\epsilon}p$ והריצה מגיעה ל- $q$ , היא יכולה להישאר ב- $q$ או להמשיך ב- $p$ .
מעברי $\epsilon$ במהותם הם אי דטרמיניסטים, לכןף הם אינם קיימים באוטומט סופי דטרמיניסטי.
אפשר לעבור במעברי $\epsilon$ לפני/באמצע/בסוף המילה.
מותר לעבור בכמה מעברי $\epsilon$ ברצף.

נקרא למודל $\epsilon-NFA$ ונראה: $\epsilon-NFA\equiv NFA$ .

הגדרה 22 (

\epsilon-NFA

)

A=(Q,\Sigma,I,R,F)

ההבדל היחיד בין $NFA$ לאוטומט הנוכחי הוא:

R \subseteq Q\times(\Sigma \cup \left\{ \epsilon \right\})\times Q

טענה

$L$ היא רגולרית $\iff$ קיים $\epsilon-NFA$ כך ש- $L(A)=L$ .

רעיון הוכחה:
נראה תרגום בין $NFA$ ל- $\epsilon-NFA$ .
⇐: יהי אוטומט סופי לא דטרמיניסטי $A$ . הוא $\epsilon-NFA$ שאין בו מעברי $\epsilon$ . כלומר, $NFA$ הוא מקרה פרטי של $\epsilon-NFA$ .
⇒: יהי $A$ אוטומט סופי לא דטרמיניסטי בעל מעברי $\epsilon$ . אנו נבנה אוטומט סופי לא דטרמיניסטי ללא מעברי $\epsilon$ בעזרת שני השינויים הבאים:

אם אפשר להגיע ל- $q$ ממצב התחלתי ע"י קריאה של $\epsilon$ -ים בלבד: $q$ יהיה מצב התחלתי.
אם אפשר להגיע ממצב $q$ למצב $p$ ע"י קריאה של אות $\sigma$ (כלומר מתקיים $q \xrightarrow{\epsilon}q'\xrightarrow{\sigma}p'\xrightarrow{\epsilon}p$ ) נוסיף מעבר ישיר עם $\sigma$ מ- $q$ ל- $p$ .

הוכחה:
יהי $\epsilon-NFA$ :

A=(Q,\Sigma,I,R,F)

נבנה אוטומט סופי דטרמיניסטי $B$ כך:

B=(Q,\Sigma,I',R',F)

כאשר:

I'=\left\{ \begin{array}{c|c} q & \exists\ p \in I:\; p \overunderset{\epsilon}{A}{\longrightarrow}q \end{array} \right\}

נשים לב שכל $q \in I$ שייך ל- $I'$ .

R'=\left\{ \begin{array}{c|c} (q,\sigma,p) & q \overunderset{\sigma}{A}{\longrightarrow} p \end{array} \right\}

נשים לב כי הם לאו דווקא מחוברים בעזרת מעבר ישיר.
הוכחת נכונות: ניתן להראות כי לכל $w$ ולכל מצב $p$ :
קיים $q \in I$ כך ש- $\iff q \overunderset{w}{A}{\longrightarrow}p$ קיים $q'\in I'$ כך ש- $q \overunderset{w}{B}{\longrightarrow}p$ .
מסקנה: $\iff w \in L(A)$ קיים $q \in I,p \in F$ כך ש- $q \overunderset{w}{A}{\longrightarrow}p$ $\iff$ קיים $q'\in I'$ ו- $p \in F$ כך ש- $q' \overunderset{w}{B}{\longrightarrow}p$ $\iff$ $w \in L(B)$ .
∎

דוגמה

כעת נראה למה הוא יהפוך ( $B$ )

שימושים למעברי $\epsilon$

הערה (תזכורת)

הגדרנו שרשור שפות כך:

\begin{align*} L_{1} \circ L_{2} & =\left\{ u \circ v| u \in L_{1} \land v \in L_{2} \right\} \\ & =\left\{ w| \exists u \in L_{1} \land \exists v \in L_{2}:\; w=uv \right\} \end{align*}

טענה

אם $L_{1},L_{2}$ רגולרית אז $L_{1} \circ L_{2}$ רגולרית.

הוכחה:
בהנתן $A_{1}=(Q_{1},\Sigma,I_{1},R_{1},F_{1})$ ו- $A_{2}=(Q_{2},\Sigma,I_{2},R_{2},F_{2})$ אוטומטים סופיים לא דטרמינסיטיים.
נבנה $\epsilon-NFA$ כך

A=(Q_{1} \cup Q_{2},\Sigma,I_{1},\mathbf{R},F_{2})

\mathbf{R}=R_{1}\cup R_{2}\cup \left\{ (q,\epsilon,p)|q \in F_{1} \land p \in I_{2} \right\}

נוכיח נכונות:
⇐: נניח $w \in L_{1} \circ L_{2}$ . אזי, מההגדרה: קיימת $u \in L_{1}$ וקיימת $v \in L_{2}$ כך ש- $w=uv$ .

u \in L_{1} \implies \exists q_{0} \in I_{1} \land \exists q \in F_{1}:\; q_{0} \overunderset{u}{A_{1}}{\longrightarrow}q

v \in L_{2} \implies \exists p_{0} \in I_{2} \land \exists p \in F_{2}:\; p_{0} \overunderset{v}{A_{2}}{\longrightarrow}p

מהבנייה, קיימת ריצה:

q_{0} \xrightarrow{u}q \xrightarrow{\epsilon}p_{0} \xrightarrow{v}p

ולכן: $w \in L(A)$ .
⇒: תהי $w \in L(A)$ . אזי קיים $q_{0} \in I_{1}$ וקיים $q \in F_{2}$ כך ש- $q_{0} \overunderset{w}{A}{\longrightarrow}p$ .
מכיוון ש- $q_{0}$ ב- $Q_{1}$ ו- $p$ ב- $Q_{2}$ , הריצה חייבת לעבור במעבר $\epsilon$ שהוספנו. כלומר, קיים $q_{1} \in F_{1}$ ו- $p_{0} \in I_{2}$ כך ש- $w$ ניתנת לפירוק: $w=uv$ כך ש:

q_{0} \xrightarrow{u}q \xrightarrow{\epsilon}p_{0} \xrightarrow{v}p

מהבניה קיבלנו כי:

u \in L(A_{1}) \land v \in L(A_{2})

ולכן, $w \in L_{1} \circ L_{2}$ .
∎

הערה (תזכורת)

L^*=\bigcup_{i\geq 0}L^i=L^0 \cup L^1 \cup \dots

כלומר, שפת כל השרשורים (באורך סופי כלשהו) של מילים מ- $L$ .

טענה

אם $L$ רגולרית ⇐ $L^*$ רגולרית.

רעיון:
2 - אוטומטים 2026-01-11 12.10.51.excalidraw.svg
הוכחה:

A=(Q,\Sigma,I,R,F)

A'=(Q \cup \left\{ p \right\}, \Sigma,I \cup \left\{ p \right\},R',F \cup \left\{ p \right\})

R'=R \cup \left\{ (q,\epsilon,p)| q \in F \land p \in I \right\}

סקיצת הוכחת נכונות:

אם $w \in L^*$ : אם $w=\epsilon$ אזי מתקבלת ע"י $p$ ⇐ $w \in L(A')$ . אחרת, $w=u_{1}u_{2}\dots u_{k}$ וכולן ב- $L$ . לכל אחת מהן ריצה מקבלת $q_{0}^i \xrightarrow{u_{i}}p_{i}$ ב- $A$ . נדביק אותן יחד: $q_{0}^1 \xrightarrow{u_{1}}p_{1}\xrightarrow{\epsilon}q_{0}^2\xrightarrow{u_{2}}p_{2}\dots \xrightarrow{u_{k}}p_{k}$ וזו ריצה מקבלת על $w$ .
אם $w \in L(A')$ : אם הגיעה ל- $p$ : $w=\epsilon$ ⇐ $w \in L^*$ . אחרת, נפרק את הריצה המקבלת עליה לפי מעברי $\epsilon$ : $q_{0}\xrightarrow{u_{1}}\xrightarrow{\epsilon}\xrightarrow{\epsilon}\dots \xrightarrow{\epsilon}\xrightarrow{u_{k}}p$ . מהבניה: $u_{i}\in L$ לכל $1\leq i\leq k$ ⇐ $w \in L^*$ .
∎

ביטויים רגולריים

ביטויים רגולרים הם עוד דרך להציג שפה. רק שבמקום שנשתמש במודל חישובי, נשתמש בביטויים.
יהי $\Sigma$ א"ב. תחילה נרצה לגדיר קבוצת ביטויים רגולריים $R_{\Sigma}$ מעל $\Sigma$ :
בסיס: $\emptyset,\epsilon$ הם ביטויים רגולריים. בנוסף, לכל $\sigma \in\Sigma$ : $\sigma \in R_{\Sigma}$ .
צעד: אם $r_{1},r_{2} \in R_{\Sigma}$ אזי הביטויים הבאים גם ב- $R_{\Sigma}$ :

(r_{1}+r_{2}), \qquad (r_{1}\cdot r_{2}), \qquad (r_{1}^*)

דוגמה

נקח את $\Sigma=\left\{ a,b \right\}$ . ביטויים רגולרים ב- $R_{\Sigma}$ :

\begin{align*} & a,b,\emptyset,\epsilon, \\ & (a+b),(\epsilon\cdot b),(\emptyset^*),(b\cdot b), \\ & ((a+b)\cdot\epsilon),((a+b)^*),((b\cdot b)+(e\cdot b)), \\ & (((a+b)\cdot\epsilon)^*) \end{align*}

וכו וכו'.

נראה פה כי לכל ביטוי רגולרי $r \in R_{\Sigma}$ אפשר להתאים עץ יצירה (לא נגדיר, רק נדגים):

((b\cdot b)+(b\cdot \epsilon)):

לכל ביטוי יש עץ יצירה יחיד.

המשמעות של ביטויים רגולריים

לכל $r \in R_{\Sigma}$ נתאים שפה $L[r]$ מעל $\Sigma$ :
בסיס: $L[\epsilon]=\left\{ \epsilon \right\},L[\emptyset]=\emptyset$ ובנוסף, $\forall\sigma \in\Sigma:\; L[\sigma]=\left\{ \sigma \right\}$ .
צעד: $r_{1},r_{2} \in R_{\Sigma}$ . נגדיר:

L[(r_{1}\cdot r_{2})]=L[r_{1}]\cdot L[r_{2}]

L[(r_{1}^*)]=L[r_{1}]^*

L[(r_{1}+r_{2})]=L[r_{1}]\cup L[r_{2}]

דוגמה

L[(((a+b)\cdot b)^*)]=L[((a+b)\cdot b)]^*=(L[(a+b)]\cdot L[b])^*=((L[a] \cup L[b])\cdot L[b])^*

=((\left\{ a \right\}\cup \left\{ b \right\})\cdot \left\{ b \right\})^*=(\left\{ a,b \right\}\cdot \left\{ b \right\})^*=\left\{ ab,bb \right\}^*

דוגמה (עוד דרך עבודה שהיא קצת יותר נוחה)

נסתכל על עץ הבנייה של הביטוי:

נוכל לכתוב ליד כל עלה בעץ את הקבוצה המתאימה וכך לבנות.

כעת, נוכל להגדיר שפות רגולריות ונבנה עבורן ביטויים.
נתחיל עם השפה $\left\{ a,b \right\}^*$ :

((a+b)^*)

נכתוב ביטוי עבור שפת כל המילים מעל $\left\{ a,b \right\}$ שמתחילות ב- $a$ ונגמרות ב- $b$ :

((a\cdot ((a+b)^*))\cdot b)

הערה

באופן לא פורמלי, נסיר סוגריים מיותרים. (כגון הסוגריים החיצוניים)

במקרה הזה נכתוב:

a\cdot(a+b)^* \cdot b

נכתוב ביטוי עבור שפת כל המילים שיש להן תת-מילה $ab$ :

(a+b)^* \cdot a\cdot b\cdot (a+b)^*

נכתוב ביטוי עבור שפת כל המילים באורך אי-זוגי:

\underbrace{((a+b)\cdot(a+b))^*}_{\begin{matrix} \R{\text{שרשורים של כל המילים באורך 2}} \\ || \\ \R{\text{כל המילים באורך זוגי}} \end{matrix}}\cdot(a+b)

נכתוב ביטוי לשפת כל המילים שיש בהן מספר זוגי של $a$ :

(b^*ab^*ab^*)^* + b^*

שקילות בין שפות רגולריות וביטויים רגולריים

משפט

יהי $\Sigma$ א"ב.
שפה $L$ מעל $\Sigma$ היא רגולרית $\iff$ קיים ביטוי רגולרי $r \in R_{\Sigma}$ כך ש- $L[r]=L$ .

הוכחה:
⇒: יהי $r \in R_{\Sigma}$ . נחלק למקרים לפי מבנה $r$ :

אם $r$ בסיס: $r \in \left\{ \epsilon,\emptyset,\sigma \right\}$ עבור $\sigma \in\Sigma$ כלשהי. בכל המקרים הללו:
$L[\epsilon]=\left\{ \epsilon \right\} \qquad L[\emptyset]=\emptyset \qquad L[\sigma]=\left\{ \sigma \right\}$
הוכנו כבר בעבר שכל הביטויים הללו הם רגולריים.
אחרת: $r=(r_{1}+r_{2})\lor r=(r_{1}\cdot r_{2})\lor r=(r_{1}^*)$ עבור $r_{1},r_{2} \in R_{\epsilon}$ כלשהם.
נניח כי $L[r_{1}],L[r_{2}]$ הן רגולריות. הראנו ששפות רגולריות סוגורות תחת $\cup,\cdot,^*$ ולכן בכל אחד מהמקרים: $L[r]$ רגולרית.

⇐: תהי $L$ שפה רגולרית. נבנה $r$ כך ש- $L[r]=L$ . נציג אלגוריתם לבניית $r$ על סמך אוטומט סופי לא דטרמיניסטי עבור $L$ .

יהי אוטומט סופי לא דטרמיניסטי $A$ עבור $L$ . נוסיף מצב מקבל חדש, אליו עוברים בכל מעבר למצב מקבל ב- $A$ והוא יהיה המקבל היחיד. נוסיף גם התחלתי יחיד שעובר לכל המצבים שאפשר להגיע אליהם מהמצב ההתחלתיים ב- $A$ ואם הם הגיעו למצב מקבל: גם לחדש. בנוסף, אם קיים מצב התחלתי מקבל, נוסיף מעבר- $\epsilon$ למקבל החדש.
נמחק מצבים באופן הבא: לכל מצב(מקורי) ולכל

נבצע:

p \xrightarrow{r_{1}\cdot r_{2}^\cdot r_{3}}q

בשלב השני של מחיקת המצבים, לכל $p,q$ שיש ביניהם אוסף של מעברים $r_{1},r_{2},\dots,r_{k}$ נחליף אותם במעבר $p \xrightarrow{r_{1}+\dots+r_{k}}q$ .
נחזור על שלב 2 עד אשר לא ישאר לנו רק מעבר אחד.
הביטוי שיהיה מעל המעבר יהיה הביטוי הרגולרי של האוטומט.
∎

דוגמה (לבניית אוטומט)

נקח עץ שרשור:
2 - אוטומטים 2026-01-25 11.45.38.excalidraw.svg

2 - אוטומטים

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

אוטומטים

2 - אוטומטים

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

אוטומטים

הקדמה - מהי בעיה חישובית

שפות ומילים

פעולות על מילים ושפות

שרשור מילים

חזקה של מילים

שרשור שפות

חזקה של שפות

אוטומטים

אוטומט סופי

דטרמיניסטי

פונקציית המעברים המורחבת

שפות רגולריות

תכונות של שפות רגולריות

1. סגירות תחת השלמה.

2. סגירות תחת חיתוך

3. סגירות תחת איחוד

3.1 איחוד סופי

שפות לא רגולריות

שיטות להוכחת רגולריות או אי-רגולריות של שפות

למת הניפוח לשפות רגולריות

משפט מייהיל-נרוד

יחס מייהיל-נרוד של שפה $L$

המשפט

דגשים

אי-דטרמיניסטי

שימושי $NFA$

בניות בעזרת $NFA$

הוכחת סגירות רגולריות להיפוך

מעברי $\epsilon$

שימושים למעברי $\epsilon$

ביטויים רגולריים

המשמעות של ביטויים רגולריים

שקילות בין שפות רגולריות וביטויים רגולריים

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

אוטומטים

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

אוטומטים

הקדמה - מהי בעיה חישובית

שפות ומילים

פעולות על מילים ושפות

שרשור מילים

חזקה של מילים

שרשור שפות

חזקה של שפות

אוטומטים

אוטומט סופי

דטרמיניסטי

פונקציית המעברים המורחבת

שפות רגולריות

תכונות של שפות רגולריות

1. סגירות תחת השלמה.

2. סגירות תחת חיתוך

3. סגירות תחת איחוד

3.1 איחוד סופי

שפות לא רגולריות

שיטות להוכחת רגולריות או אי-רגולריות של שפות

למת הניפוח לשפות רגולריות

משפט מייהיל-נרוד

יחס מייהיל-נרוד של שפה LLL

המשפט

דגשים

אי-דטרמיניסטי

שימושי NFANFANFA

בניות בעזרת NFANFANFA

הוכחת סגירות רגולריות להיפוך

מעברי ε\epsilonε

שימושים למעברי ε\epsilonε

ביטויים רגולריים

המשמעות של ביטויים רגולריים

שקילות בין שפות רגולריות וביטויים רגולריים

יחס מייהיל-נרוד של שפה $L$

שימושי $NFA$

בניות בעזרת $NFA$

מעברי $\epsilon$

שימושים למעברי $\epsilon$