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

תרגיל

הוכיחו באמצעות לכסון שהקבוצה הבאה אינה בת מניה.

A=\left\{ L \subseteq \left\{ 0,1 \right\}^*| \forall w \in L:\; \#_{0}[w]\equiv 0 (mod\; 2) \right\}

הדרך הנכונה להסתכל על קבוצות היא גם על ידי וקטור אינסופי. אחרי שאנו נבהלים מזה שהביאו לנו שפות אנו מבינים כי עלינו ללכסן קבוצה.
לפני שנתחיל נעשה סקירה של איך מלכסנים כאשר מדובר קבוצת קבוצות:
[...] תהי $g:\mathbb{N}\to A$ . אנו נרצה להראות כי $g$ אינה על.
כאשר $A$ היא קבוצה של קבוצות, אנו יכולים להסתכל על $A$ כך: $A=\left\{ B | B \subseteq W \right\}$ . נניח ש- $W$ היא בת מניה.

הערה

נשים לב כי זה גם מתרחש במקרה שלנו שכן $\left\{ 0,1 \right\}^*$ היא בת מנייה.

נשרטט לנו טבלה שכזו, בה כל עמודה היא מילה ב- $w$ .

W=\left\{ w_{0},\quad w_{1},\quad w_{2},\quad \dots \right\}

ואז, לכל אינדקס, נבדוק האם המילה נמצאת ב- $g(n)$ ואם לא, נוסיף אותה לקבוצה שאנו יוצרים על מנת להראות כי $g$ אינה על.

\begin{array}{|c|c|} \hline w_{0} & w_{1} & w_{2} & \dots \\ \hline g(0)= & \xcancel{}/\checkmark \\ \hline g(1)= \\ \hline \vdots \end{array}

לפעמים, נוכל לצמצם את $W$ עוד יותר כדי לוותר מראש על מקרים לא רלוונטיים. במקרה שלנו, נוכל להתמקד בקבוצה $\left\{ 0^{2i}|i \in \mathbb{N} \right\}$ . השפות ב- $A$ לאו דווקא מוכלות בקבוצה החדשה שלנו, אבל מספיק לנו לקלקל את האיברים המופיעים בה על מנת לראות שהקבוצה אינה בת מניה.
כעת, אנו ערוכים ללכסן. אנו נבנה שפה $L$ כך ש- $L \in A$ ו- $\forall i \in \mathbb{N}:\; L\neq g(i)$ .

L=\left\{ 0^{2i}| i \in \mathbb{N},\; 0^{2i} \not\in g(i) \right\}

נראה את זה ויזואלית:

\begin{matrix} & 0^0 & 0^2 & 0^4 & 0^6 & 0^8 & \dots \\ g(0)= & \boxed{\xcancel{}} & \checkmark & \checkmark & \xcancel{} & \checkmark & \dots \\ g(1)= & \checkmark & \boxed{\checkmark} & \xcancel{} & \checkmark & \checkmark & \dots \\ g(2)= & \xcancel{} & \xcancel{} & \boxed{\xcancel{}} & \checkmark & \xcancel{} & \dots \end{matrix}

נקבל כי: $L=\left\{ \epsilon,0^4,\dots \right\}$
נקבל כי $L \subseteq \left\{ 0^{2i}|i \in \mathbb{N} \right\}$ ולכן, $L \in A$ : כל המילים בעלות מס' זוגי של $0$ .
לכל $i \in \mathbb{N}$ : $0^{2i}\not\in g(i)\iff 0^{2i}\in L$ . כלומר, לכל $i \in \mathbb{N}$ $g(i)$ ו- $L$ לא מסכימות על $0^{2i}$ ⇐ $g(i)\neq L$ ולכן, $g$ אינה על.

וקטור מייצג: אם $B \subseteq A$ ו- $A$ ב"מ, אפשר לתאר את $B$ כווקטור:

\begin{matrix} A: & a_{0} & a_{1} & a_{2} & a_{3} & \dots \\ B: & \underbracket{0/1}_{\R{בהתאמה}} & \dots \end{matrix}

ואז: $A=\left\{ 1,2,3,4,5 \right\}$ ו- $B=\left\{ 2,5 \right\}$ :

B:(0,1,0,0,1)

הערה (דרכים להוכיח ששפה היא רגולרית)

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

תרגיל

נסמן $B=\mathbb{N}^{\mathbb{N}}$ . נגדיר את התומך של $f$ להיות: $S_{f}=\left\{ n|f(n)\neq 0 \right\}$ (קבוצת כל האיברים שאינם נשלחים ל- $0$ )
הוכיחו כי הקבוצה הבאה הינה בת מנייה

Y=\left\{ f \in B| \R{\text{ סופית}}S_{f} \right\}

הערה (הבחנה)

$\iff f \in Y$ קיים $j \in \mathbb{N}$ כך שלכל $j'>j$ מתקיים $f(j')=0$
נוכל להוכיח על סמך האינדקס המקסימלי ב- $S_{f}$ .

נגדיר: $Y_{i}=\left\{ f|\R{\text{ מקבלת 0 מ-i והלאה}} f\right\}$ .
מתקיים: $Y=\bigcup_{i\geq 0}Y_{i}$ . כעת נותר לנו להראות רק כי כל קבוצה $Y_{i}$ היא בת מנייה.

הערה (אינטואיציה)

תהי $f \in Y_{i}$ אז $f$ ניתנת לתיאור ע"י $i$ האינדקסים הראשונים שלה.

נגדיר: $g_{i}:Y_{i}\to \mathbb{N}^i$ חח"ע.

דוגמה

f(i)=\begin{cases} 2i & i\leq 4 \\ 0 & i>4 \end{cases}

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

\begin{matrix} f: & {\color{red}(}0 & 2 & 4 & 6 & 8{\color{red})} & 0 & 0 & 0 & \dots \end{matrix}

זהו וקטור מ- $\mathbb{N}^5$ .

משפט (שלמדנו)

לכל $i \in \mathbb{N}$ : $\mathbb{N}^i$ בת מנייה.

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

כמובן שצריך שהכל יהיה פורמלי

לכל $f \in Y_{i}$ :

g(f)=(f(0),f(1),\dots,f(i-1))

נוכיח כעת כי $g$ חח"ע:
יהיו $f_{1},f_{2} \in Y_{i}$ כך ש- $g(f_{1})=g(f_{2})$ . נוכיח כי $f_{1}=f_{2}$ .
אז מהגדרת $g$ , לכל $0\leq k\leq i$ מתקיים כי $f_{1}(k)=f_{2}(k)$ ולכל $k\geq i$ : $f_{1}(k)=f_{2}(k)=0$ מהשתייכותן ל- $Y_{i}$ .
⇐ לכל $k \in \mathbb{N}$ : $f_{1}(k)=f_{2}(k)$ ⇐(הגדרת שוויון פונקציות) $f_{1}=f_{2}$ .
לכן, $g$ חח"ע לפי הגדרה.

הערה (שרי אמרה)

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

תרגיל

השפות $L_{0,1,2}$ רגולריות מעל $\Sigma=\left\{ a,b \right\}$ .

L=\left\{w\#^{k}|w \in \Sigma^*, w \in L_{k (mod\; 3)} \right\}

מעל $\left\{ a,b,\# \right\}$ . הוכיחו שהשפה רגולרית.
דוגמה: $aba\#^{15}$ (הערה: סולמית פה היא תו ולא מספר ה...) שייכת ל- $L$ $\iff$ $aba \in L_{0}$ .

ישנם כל מני דרכים לעשות זאת. ננסה באמצעות $\epsilon-NFA$ .
שעת קבלה של שרי מדמקה 2026-02-16 11.03.54.excalidraw.svg
זוהי דרך קצת פחות טובה שכן כעת נדרש להוכיח שהשפה מתאימה.
נוכל בעוד דרכים כגון:

אוטומט מכפלה: רצים על שלושתם בו"ז ולפי המצבים המקבלים, להחליט כמה $\#$ לקרוא. ("זה פח" - שרי)
ביטויים רגולריים: נקח $r_{i}$ כביטוי הרגולרי עבור $L_{i}$ . ואז:
$r=r_{0}(\#\#\#)^*+r_{1}(\#\#\#)^*\#+r_{2}(\#\#\#)^*\#\#$
נדרש לעוד שתי שורות נימוק ואז סיימנו.

תרגיל

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

L=\left\{ \begin{array}{c|c} a^ib^j & i> j \end{array} \right\}

הערה

נשים לב ש- $xy^2z$ לא יעבוד לנו עם השפה הזו ונדרש לקחת חזקה אחרת לניפוח שלנו.

נניח בשלילה כי $L$ רגולרית.
יהי $n\geq 1$ קבוע המובטח ע"י למת הניפוח. נבחר: $a^{n+1}b^n$ . יהי $xyz$ פירוק של המילה כך ש- $|xy|\leq n$ וגם $y\neq \epsilon$ . ולכן, $x$ יהיה רצף של $a$ -ים, $y$ יהיה רצף של- $a$ -ים ו- $z$ יהיה רצף של $a$ -ים ואז $b$ -ים. נכתוב:

s+t\leq n,\; t>0 \qquad a^sa^ta^{n+1-s-t}b^n

נבחר: $i=0$ ואז:

a^s{a^t}^0a^{n+1-s-t}b^n=a^{n+1-t}b^n

מכיוון ש- $t>0$ נקבל כי $n+1-t\leq n$ ולכן, $a^{n+1-t}b^n \not\in L$ בסתירה ללמת הניפוח. לכן, $L$ אינה רגולרית.

תרגיל

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

טענה: מתקיימים תנאי למת הניפוח החל מ- $i=2$ .

תהי $w \in L$ כך ש- $|w|\geq2$ .

\overbrace{aa\dots a}^{i}b\dots bc\dots c

אם $i>0$ נקבע: $x=\epsilon$ , $y=a$ ו- $=z$ כל היתר.
אחרת, $b\dots bc\dots c$ ופה ברור שניתן לנפח(כי היא רגולרית).

הערה

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

תרגיל

הוכיחו באמצעות לכסון שהקבוצה הבאה אינה בת מניה.

A=\left\{ L \subseteq \left\{ 0,1 \right\}^*| \forall w \in L:\; \#_{0}[w]\equiv 0 (mod\; 2) \right\}

הערה

נשים לב כי זה גם מתרחש במקרה שלנו שכן $\left\{ 0,1 \right\}^*$ היא בת מנייה.

נשרטט לנו טבלה שכזו, בה כל עמודה היא מילה ב- $w$ .

W=\left\{ w_{0},\quad w_{1},\quad w_{2},\quad \dots \right\}

ואז, לכל אינדקס, נבדוק האם המילה נמצאת ב- $g(n)$ ואם לא, נוסיף אותה לקבוצה שאנו יוצרים על מנת להראות כי $g$ אינה על.

\begin{array}{|c|c|} \hline w_{0} & w_{1} & w_{2} & \dots \\ \hline g(0)= & \xcancel{}/\checkmark \\ \hline g(1)= \\ \hline \vdots \end{array}

L=\left\{ 0^{2i}| i \in \mathbb{N},\; 0^{2i} \not\in g(i) \right\}

נראה את זה ויזואלית:

\begin{matrix} & 0^0 & 0^2 & 0^4 & 0^6 & 0^8 & \dots \\ g(0)= & \boxed{\xcancel{}} & \checkmark & \checkmark & \xcancel{} & \checkmark & \dots \\ g(1)= & \checkmark & \boxed{\checkmark} & \xcancel{} & \checkmark & \checkmark & \dots \\ g(2)= & \xcancel{} & \xcancel{} & \boxed{\xcancel{}} & \checkmark & \xcancel{} & \dots \end{matrix}

וקטור מייצג: אם $B \subseteq A$ ו- $A$ ב"מ, אפשר לתאר את $B$ כווקטור:

\begin{matrix} A: & a_{0} & a_{1} & a_{2} & a_{3} & \dots \\ B: & \underbracket{0/1}_{\R{בהתאמה}} & \dots \end{matrix}

ואז: $A=\left\{ 1,2,3,4,5 \right\}$ ו- $B=\left\{ 2,5 \right\}$ :

B:(0,1,0,0,1)

הערה (דרכים להוכיח ששפה היא רגולרית)

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

תרגיל

Y=\left\{ f \in B| \R{\text{ סופית}}S_{f} \right\}

הערה (הבחנה)

$\iff f \in Y$ קיים $j \in \mathbb{N}$ כך שלכל $j'>j$ מתקיים $f(j')=0$
נוכל להוכיח על סמך האינדקס המקסימלי ב- $S_{f}$ .

הערה (אינטואיציה)

תהי $f \in Y_{i}$ אז $f$ ניתנת לתיאור ע"י $i$ האינדקסים הראשונים שלה.

נגדיר: $g_{i}:Y_{i}\to \mathbb{N}^i$ חח"ע.

דוגמה

f(i)=\begin{cases} 2i & i\leq 4 \\ 0 & i>4 \end{cases}

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

\begin{matrix} f: & {\color{red}(}0 & 2 & 4 & 6 & 8{\color{red})} & 0 & 0 & 0 & \dots \end{matrix}

זהו וקטור מ- $\mathbb{N}^5$ .

משפט (שלמדנו)

לכל $i \in \mathbb{N}$ : $\mathbb{N}^i$ בת מנייה.

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

כמובן שצריך שהכל יהיה פורמלי

לכל $f \in Y_{i}$ :

g(f)=(f(0),f(1),\dots,f(i-1))

הערה (שרי אמרה)

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

תרגיל

השפות $L_{0,1,2}$ רגולריות מעל $\Sigma=\left\{ a,b \right\}$ .

L=\left\{w\#^{k}|w \in \Sigma^*, w \in L_{k (mod\; 3)} \right\}

אוטומט מכפלה: רצים על שלושתם בו"ז ולפי המצבים המקבלים, להחליט כמה $\#$ לקרוא. ("זה פח" - שרי)
ביטויים רגולריים: נקח $r_{i}$ כביטוי הרגולרי עבור $L_{i}$ . ואז:
$r=r_{0}(\#\#\#)^*+r_{1}(\#\#\#)^*\#+r_{2}(\#\#\#)^*\#\#$
נדרש לעוד שתי שורות נימוק ואז סיימנו.

תרגיל

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

L=\left\{ \begin{array}{c|c} a^ib^j & i> j \end{array} \right\}

הערה

נשים לב ש- $xy^2z$ לא יעבוד לנו עם השפה הזו ונדרש לקחת חזקה אחרת לניפוח שלנו.

s+t\leq n,\; t>0 \qquad a^sa^ta^{n+1-s-t}b^n

נבחר: $i=0$ ואז:

a^s{a^t}^0a^{n+1-s-t}b^n=a^{n+1-t}b^n

מכיוון ש- $t>0$ נקבל כי $n+1-t\leq n$ ולכן, $a^{n+1-t}b^n \not\in L$ בסתירה ללמת הניפוח. לכן, $L$ אינה רגולרית.

תרגיל

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

טענה: מתקיימים תנאי למת הניפוח החל מ- $i=2$ .

תהי $w \in L$ כך ש- $|w|\geq2$ .

\overbrace{aa\dots a}^{i}b\dots bc\dots c

אם $i>0$ נקבע: $x=\epsilon$ , $y=a$ ו- $=z$ כל היתר.
אחרת, $b\dots bc\dots c$ ופה ברור שניתן לנפח(כי היא רגולרית).

הערה