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

NFA

))

נגדיר אוטומט סופי לא דטרמיניסטי בצורה הבאה:

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

ישנם שני הבדלים בינו לבין אוטומט סופי דטרמיניסטי:

במקום מצב התחלתי יחיד $q_{0}$ , יש לנו קבוצת מצבים התחלתיים $I$ .
במקום פונקצית מעברים $\delta$ , יש לנו יחס מעברים $R \subseteq Q\times\Sigma \times Q$ . כאשר אם $(q,\sigma,p)\in R$ אזי זה אומר כי ניתן לעבור מ- $q$ ל- $p$ ע"י קריאת $\sigma$ ונסמן זאת: $q \overset{\sigma}{\longrightarrow}p$ .

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

דוגמה

איך נראה שהאוטומט הזה הוא אוטומט לא דטרמיניסטי? כי אין לכל מצב קשת, נניח, אם נקבל $0$ או $1$ ב- $q_{1}$ וגם נראה כי יש שני דרכים שבהם נוכל ללכת מ- $q_{0}$ עם 1.
עבור $\Sigma=\left\{ 0,1,2 \right\}$ - נשים לב כי לא באמת נוכל לדעת את שפת האוטומט מאוטומט סופי לא דטרמיניסטי בלבד, שכן יכולות להופיע עוד אותיות אשר להן לא יהיו קשתות

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

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

S_{0}\xrightarrow{\sigma_{1}}S_{1}\xrightarrow{\sigma_{2}}\dots \xrightarrow{\sigma_{n}}S_{n}

כך ש- $S_{0}\in I$ ולכל $1\leq i\leq n$ מתקיים $(S_{i-1},\sigma_{i},S_{i})\in R$ .
נסמן גם: $S_{0}\overset{w}{\longrightarrow}S_{n}$ .

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

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

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

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

דוגמה

בדוגמה שראינו ממקודם מתקיים כי השפה של $A$ היא:

L(A)=\left\{ 0,1 \right\}^* \circ \left\{ 1 \right\}

נסתכל על אילו מסלולי ריצה יש לנו עבור $w=0101$ :

נוכל להישאר ב- $q_{0}$ במהלך כל המילה, מה שיתן לנו ריצה לא מקבלת.
נוכל לעבור ל- $q_{1}$ בפעם הראשונה שאנו מקבלים 1, מה ישתן לנו ריצה שלא תתקיים. - היא לא נחשבת ריצה
נוכל לעבור ל- $q_{1}$ באות האחרונה במילה וזוהי ריצה מקבלת.

מכיוון שקיימת ריצה מקבלת, המילה $w$ בשפה.

שקילות בין $NFA$ ל- $DFA$

בהרצאה ראינו כי שני המודלים שקולים ולכן:

בהנתן אוטומט סופי דטרמיניסטי $A$ ניתן לבנות אוטומט סופי לא דטרמיניסטי $A'$ כך ש- $L(A)=L(A')$ , בצורה הבאה:
$A=(Q,\Sigma,q_{0},\delta,F)$
$A'=(Q,\Sigma,\left\{ q_{0} \right\},\delta,F)$
נזכור כי פונקציה היא מקרה פרטי של יחס.
בהנתן אוטומט סופי לא דטרמיניסטי $A$ , ניתן לבנות אוטומט סופי דטרמיניסטי $A_{D}$ כך ש- $L(A)=L(A_{D})$ באופן הבא:
נשתמש באוטומט החזרה. הרעיון הוא שאם ב- $NFA$ היו מספר ריצות אפשריות עבור מילה, נאחד את כל האפשרויות כך שיוצגו ע"י מצב יחיד ב- $DFA$ .

לשם כך, נרצה שהמצבים של ה- $DFA$ יהיו תתי קבוצות של המצבים ב- $NFA$ . נגדיר את המצבים בדטרמינסיטי להיות קבוצת החזקה של קבוצת המצבים בלא דטרמיניסטי(ומכאן השם אוטומט החזקה)

בנייה פורמלית של אוטומט החזקה

בהנתן אוטומט סופי לא דטרמיניסטי: $A=(Q,\Sigma,I,R,F)$ נגדיר $A_{D}=(Q_{D},\Sigma,q_{0},\delta,F_{D})$ כאשר:

Q_{D}=P(Q) \qquad q_{0}=I \qquad F_{D}=\left\{ S \subseteq Q\ |\ S \cap F\neq \emptyset \right\}

לכל $S_{i}\in P(Q)$ ולכל $\sigma \in \Sigma$ :

\delta(S_{i},\sigma)=\left\{ P \in Q_{D}|\exists q \in S:\; q \overunderset{\sigma}{A}{\longrightarrow}p \right\}

כלומר, ממצב $S \in P(Q)$ עם אות $\sigma$ עוברים לכל המצבים ב- $Q$ שהיה מעבר ממצב ב- $S$ אליהם.

דוגמה

נבנה אוטומט סופי דטרמיניסטי עבור האוטומט הלא דטרמיניסטי שראינו קודם מעל $\Sigma=\left\{ 0,1 \right\}$ .
כמה מצבים יהיו באוטומט החזקה?

|P(Q)|=|2^Q|=2^{|Q|}=2^2=4

זה נכון רק אם $Q$ סופית. (והיא סופית כי זה $NFA$ )

נשים לב כי יש לנו פה שני מצבים מיותרים $\left\{ q_{1} \right\}$ ו- $\left\{ \emptyset \right\}$ .
מה יקרה אם נקח $\Sigma=\left\{ 0,1,2 \right\}$ במקום?

איך מוכיחים שפה של $NFA$ ?

באמצעות הכלה דו כיוונית.
כיוון 1: $L \subseteq L(A)$ . לוקחים מילה מ- $L$ ומראים ריצה מקבלת של $A$ על המילה.
כיוון 2: $L(A) \subseteq L$ . מניחים שיש ריצה מקבלת של $A$ ועל מילה ובעזרת מבנה $A$ מסיקים על מבנה המילה.

תרגול

תרגיל

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

א. מהי השפה של $A$ ?
ב. הוכיחו שזו אכן שפתו.

פתרון א':

L=\left\{ 0,1 \right\}^*\circ\left\{ 1 \right\}\circ\left\{ 0,2 \right\}^*\circ\left\{ 2 \right\}

הוכחה: (ב')
נוכיח $L=L(A)$ בהכלה דו כיוונית.
כיוון 1, $L \subseteq L(A)$ : תהא $w \in L$ .
ממבנה $L$ מתקיים $w=u1v2$ עבור $u \in \left\{ 0,1 \right\}^*$ ו- $v \in \left\{ 0,2 \right\}^*$ .
ריצה מקבלת של $A$ על $w$ היא למשל ריצה שתשאר ב- $q_{0}$ כל עוד קוראים $u$ , תעבור ל- $q_{1}$ כשקוראים $1$ , תשאר ב- $q_{1}$ כל עוד קוראים $v$ ותעבור ל- $q_{2}$ כשקוראים 2.

q_{0}\xrightarrow{u}q_{0}\xrightarrow{1}q_{1}\xrightarrow{v}q_{1}\xrightarrow{2}q_{2}

זו ריצה מקבלת שכן $q_{0} \in I$ ו- $q_{2}\in F$ והמעברים חוקיים ממבנה $A$ .
לכן, מהגדרת שפת $NFA$ מתקיים: $w \in L(A)$ .
כיוון 2, $L(A)\subseteq L$ : תהא $w \in L(A)$ .
מהגדרת שפת אוטומט סופי לא דטרמיניסטי, קיימת ריצה מקבלת של $A$ על $w$ . ריצה כזו תתחיל מהמצב ההתחלתי היחיד $q_{0}$ ותסתיים במצב המקבל היחיד $q_{2}$ .
כלומר קיימת $q_{0} \xrightarrow{w}q_{2}$ .
ממבנה $A$ , כדי להגיע מ- $q_{0}$ ל- $q_{2}$ חייבים לעבור דרך $q_{1}$ . מ- $q_{2}$ אין קשתות יוצאות ולכן לא יכולנו לעבור ב- $q_{2}$ לפני המצב האחרון.
נסמן $w=\sigma_{1}\dots\sigma_{n}$ ואז הריצה תראה כך:

q_{0}\xrightarrow{\sigma_{1}}S_{1}\xrightarrow{\sigma_{2}}S_{2}\dots \xrightarrow{\sigma_{n-1}}S_{n-1}\xrightarrow{\sigma_{n}}q_{2}

ממה שהסברנו קודם, קיים $1\leq i\leq n-1$ מינימאלי כך ש- $S_{i}=q_{1}$ .
ממבנה $A$ , עד למצב $S_{i}$ חייבים להשאר ב- $q_{0}$ . לכן, לכל $1\leq k\leq i$ מתקיים $S_{k}=q_{0}$ . לאחר מכן, כפי שהסברנו, חייבים להישאר ב- $q_{1}$ כי לא ניתן לצאת מ- $q_{2}$ . לכן, לכל $i<k<n$ מתקיים $S_{k}=q_{1}$ .
כדי לעבור ל- $q_{2}$ חייבים לקרוא $2$ ולכן $\sigma_{n}=2$ .
במעבר מ- $q_{0}$ ל- $q_{1}$ קוראים $1$ . כל עוד נשארים ב- $q_{0}$ קוראים 0 או 1, ובדומה, נשארים ב- $q_{1}$ כל עוד קוראים 0 או 2.
לכן, $w$ חייבת להיות $\left\{ 0,1 \right\}^*\circ\left\{ 1 \right\}\circ\left\{ 0,2 \right\}^*\circ\left\{ 2 \right\}$ וזה בדיוק $L$ ולכן $w \in L$ .
∎

תרגיל

יהא $\Sigma$ א"ב כלשהו. בנו אוטומט עבור השפה:

L=\left\{ u\sigma v\sigma w|u,v,w \in\Sigma^*,\sigma \in\Sigma \right\}

במילים: $L$ היא שפת כל המילים מעל $\Sigma^*$ שיש בהן אות שמופיעה לפחות פעמיים.

רעיון הבניה: ננחש איזו אות $\sigma$ תחזור על עצמה פעמיים. (ניחוש ⇐ $NFA$ )
פתרון:
נסמן $\Sigma=\left\{ \sigma_{1},\dots,\sigma_{n} \right\}$ (אפשרי כי א"ב היא קבוצה סופית ולא ריקה)
נגדיר אוטומט סופי לא דטרמיניסטי $A=(Q,\Sigma,I,R,F)$ כאשר:

Q=\left\{ q_{s},q_{f},q_{\sigma}|\sigma \in\Sigma \right\}

I=\left\{ q_{s} \right\}

F=\left\{ q_{f} \right\}

R=\left\{ (q,\sigma,q)|q \in Q,\sigma \in\Sigma \right\} \cup \left\{ (q_{s},\sigma,q_{\sigma})|\sigma \in\Sigma \right\} \cup \left\{ (q_{\sigma,\sigma,q_{f}})|\sigma \in\Sigma \right\}

הקבוצה השמאלית היא לולאות עצמיות אשר מאפשרות לקרוא את $u,v,w$ . הקבוצה האמצעית מאפשרת לזכור שראינו $\sigma$ והקבוצה הימנית מאפשרת לדעת שראינו את אותה $\sigma$ פעם שנייה.

תרגול

תרגיל

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

א. מהי השפה של $A$ ?
ב. הוכיחו שזו אכן שפתו.

פתרון א':

L=\left\{ 0,1 \right\}^*\circ\left\{ 1 \right\}\circ\left\{ 0,2 \right\}^*\circ\left\{ 2 \right\}

הוכחה: (ב')
נוכיח

L=L(A)

בהכלה דו כיוונית.
כיוון 1,

L \subseteq L(A)

: תהא

w \in L

.
ממבנה

L

מתקיים

w=u1v2

עבור

u \in \left\{ 0,1 \right\}^*

ו-

v \in \left\{ 0,2 \right\}^*

.
ריצה מקבלת של

A

על

w

היא למשל ריצה שתשאר ב-

q_{0}

כל עוד קוראים

u

, תעבור ל-

q_{1}

כשקוראים

1

, תשאר ב-

q_{1}

כל עוד קוראים

v

ותעבור ל-

q_{2}

כשקוראים 2.

q_{0}\xrightarrow{u}q_{0}\xrightarrow{1}q_{1}\xrightarrow{v}q_{1}\xrightarrow{2}q_{2}

זו ריצה מקבלת שכן

q_{0} \in I

ו-

q_{2}\in F

והמעברים חוקיים ממבנה

A

.
לכן, מהגדרת שפת

NFA

מתקיים:

w \in L(A)

.
כיוון 2,

L(A)\subseteq L

: תהא

w \in L(A)

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

A

על

w

. ריצה כזו תתחיל מהמצב ההתחלתי היחיד

q_{0}

ותסתיים במצב המקבל היחיד

q_{2}

.
כלומר קיימת

q_{0} \xrightarrow{w}q_{2}

.
ממבנה

A

, כדי להגיע מ-

q_{0}

ל-

q_{2}

חייבים לעבור דרך

q_{1}

. מ-

q_{2}

אין קשתות יוצאות ולכן לא יכולנו לעבור ב-

q_{2}

לפני המצב האחרון.
נסמן

w=\sigma_{1}\dots\sigma_{n}

ואז הריצה תראה כך:

q_{0}\xrightarrow{\sigma_{1}}S_{1}\xrightarrow{\sigma_{2}}S_{2}\dots \xrightarrow{\sigma_{n-1}}S_{n-1}\xrightarrow{\sigma_{n}}q_{2}

ממה שהסברנו קודם, קיים

1\leq i\leq n-1

מינימאלי כך ש-

S_{i}=q_{1}

.
ממבנה

A

, עד למצב

S_{i}

חייבים להשאר ב-

q_{0}

. לכן, לכל

1\leq k\leq i

מתקיים

S_{k}=q_{0}

. לאחר מכן, כפי שהסברנו, חייבים להישאר ב-

q_{1}

כי לא ניתן לצאת מ-

q_{2}

. לכן, לכל

i<k<n

מתקיים

S_{k}=q_{1}

.
כדי לעבור ל-

q_{2}

חייבים לקרוא

2

ולכן

\sigma_{n}=2

.
במעבר מ-

q_{0}

ל-

q_{1}

קוראים

1

. כל עוד נשארים ב-

q_{0}

קוראים 0 או 1, ובדומה, נשארים ב-

q_{1}

כל עוד קוראים 0 או 2.
לכן,

w

חייבת להיות

\left\{ 0,1 \right\}^*\circ\left\{ 1 \right\}\circ\left\{ 0,2 \right\}^*\circ\left\{ 2 \right\}

וזה בדיוק

L

ולכן

w \in L

.
∎

תרגיל

יהא $\Sigma$ א"ב כלשהו. בנו אוטומט עבור השפה:

L=\left\{ u\sigma v\sigma w|u,v,w \in\Sigma^*,\sigma \in\Sigma \right\}

במילים: $L$ היא שפת כל המילים מעל $\Sigma^*$ שיש בהן אות שמופיעה לפחות פעמיים.

רעיון הבניה: ננחש איזו אות

\sigma

תחזור על עצמה פעמיים. (ניחוש ⇐

NFA

)
פתרון:
נסמן

\Sigma=\left\{ \sigma_{1},\dots,\sigma_{n} \right\}

(אפשרי כי א"ב היא קבוצה סופית ולא ריקה)
נגדיר אוטומט סופי לא דטרמיניסטי

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

כאשר:

Q=\left\{ q_{s},q_{f},q_{\sigma}|\sigma \in\Sigma \right\}

I=\left\{ q_{s} \right\}

F=\left\{ q_{f} \right\}

R=\left\{ (q,\sigma,q)|q \in Q,\sigma \in\Sigma \right\} \cup \left\{ (q_{s},\sigma,q_{\sigma})|\sigma \in\Sigma \right\} \cup \left\{ (q_{\sigma,\sigma,q_{f}})|\sigma \in\Sigma \right\}

הקבוצה השמאלית היא לולאות עצמיות אשר מאפשרות לקרוא את

u,v,w

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

\sigma

והקבוצה הימנית מאפשרת לדעת שראינו את אותה

\sigma

פעם שנייה.

10 - אוטומט סופי לא דטרמיניסטי

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

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

10 - אוטומט סופי לא דטרמיניסטי

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

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

שקילות בין $NFA$ ל- $DFA$

בנייה פורמלית של אוטומט החזקה

איך מוכיחים שפה של $NFA$ ?

תרגול

שקילות בין $NFA$ ל- $DFA$

בנייה פורמלית של אוטומט החזקה

איך מוכיחים שפה של $NFA$ ?

תרגול

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

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

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

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

שקילות בין NFANFANFA ל-DFADFADFA

בנייה פורמלית של אוטומט החזקה

איך מוכיחים שפה של NFANFANFA?

תרגול

שקילות בין NFANFANFA ל-DFADFADFA

בנייה פורמלית של אוטומט החזקה

איך מוכיחים שפה של NFANFANFA?

תרגול

שקילות בין $NFA$ ל- $DFA$

איך מוכיחים שפה של $NFA$ ?

שקילות בין $NFA$ ל- $DFA$

איך מוכיחים שפה של $NFA$ ?