הגדרה 1

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

אוטומט מכפלה לחיתוך

בהנתן שתי שפות רגולריות $L_{1},L_{2}$ ו- $DFA$ -ים $A_{1},A_{2}$

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

A_{2}=(Q_{2},\Sigma,q_{0}^2,\delta_{2},F_{2})

L(A_{2})=L_{2},L(A_{1})=L_{1}

אז נגדיר את אוטומט המכפלה עבור $L_{1} \cap L_{2}$ כך:

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

Q=Q_{1}\times Q_{2}

q_{0}=(q_{0}^1,q_{0}^2)

F=F_{1}\times F_{2}

\forall(q,p)\in Q\; \forall\sigma \in\Sigma:\; \delta((q,p),\sigma)=(\delta_{1}(q,\sigma),\delta_{2}(p,\sigma))

מתקיים: $L(A)=L_{1} \cap L_{2}$ .

דוגמה

\Sigma=\left\{ a,b \right\}, L_{1}=\left\{ a \right\}^*,L_{2}=\left\{ b \right\}^*

כעת, נבנה אוטומט ל- $L_{1}\cap L_{2}$ .

אין זה האוטומט הכי קטן לשפה, אך הוא תמיד יעבוד.

אוטומט מכפלה לאיחוד

נשנה את $F$ להיות:

F=(F_{1}\times Q_{2})\cup(Q_{1}\times F_{2})

באוטומט שבנינו, נוכל לשנות את זה לכך ש- $q_{0}p_{1}$ ו- $q_{1}p_{0}$ יהיו מצבים מקבלים בנוסף ל- $q_{0}p_{0}$ .

תרגול

תרגיל

נתונות שתי שפות $L_{1},L_{2}$ מעל אותו א"ב $\Sigma$ .
נגדיר שפה חדשה - שפת הריצ'רץ':

L_{zip}=\left\{ \sigma_{1}\gamma_{1}\dots\sigma_{n}\gamma_{n}|\sigma_{1},\dots,\sigma_{n}\in L_{1},\gamma_{1},\dots,\gamma_{n}\in L_{2} \right\}

הוכיחו כי אם $L_{1},L_{2}$ רגולריותף אז גם $L_{zip}$ רגולרית.

הוכחה:
נתון כי $L_{1},L_{2}$ רגולריות, לכן, מהגדרה, קיימים אוטומטים סופיים דטרמיניסים $A_{1},A_{2}$ עבורן. נסמן $i \in \left\{ 1,2 \right\}$ :

A_{i}=(Q_{i},\Sigma,q_{0}^i,\delta_{i},F_{i})

ומתקיים $L(A_{i})=L_{i}$ .
נגדיר אוטומט $A$ עבור $L_{zip}$ :

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

נגדיר $Q=Q_{1}\times Q_{2}\times \left\{ 1,2 \right\}$ .
נבחר $q_{0}=(q_{0}^1,q_{0}^2,1)$ .
לכל $\sigma \in\Sigma$ ולכל $q \in Q_{1},p \in Q_{2}$ :

\begin{matrix} \delta((q,p,1),\sigma)= (\delta_{1}(q,\sigma),p,2)\\ \delta((q,p,2),\sigma)=(q,\delta_{2}(p,\sigma),1) \end{matrix}

נגדיר את $F$ להיות:

F=F_{1}\times F_{2}\times \left\{ 1 \right\}

כעת, נוכיח את נכונות האוטומט.(כלומר, נוכיח כי $L(A)=L_{zip}$ )

∎

הגדרה 1

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

אוטומט מכפלה לחיתוך

בהנתן שתי שפות רגולריות $L_{1},L_{2}$ ו- $DFA$ -ים $A_{1},A_{2}$

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

A_{2}=(Q_{2},\Sigma,q_{0}^2,\delta_{2},F_{2})

L(A_{2})=L_{2},L(A_{1})=L_{1}

אז נגדיר את אוטומט המכפלה עבור $L_{1} \cap L_{2}$ כך:

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

Q=Q_{1}\times Q_{2}

q_{0}=(q_{0}^1,q_{0}^2)

F=F_{1}\times F_{2}

\forall(q,p)\in Q\; \forall\sigma \in\Sigma:\; \delta((q,p),\sigma)=(\delta_{1}(q,\sigma),\delta_{2}(p,\sigma))

מתקיים: $L(A)=L_{1} \cap L_{2}$ .

דוגמה

\Sigma=\left\{ a,b \right\}, L_{1}=\left\{ a \right\}^*,L_{2}=\left\{ b \right\}^*

כעת, נבנה אוטומט ל- $L_{1}\cap L_{2}$ .

אין זה האוטומט הכי קטן לשפה, אך הוא תמיד יעבוד.

אוטומט מכפלה לאיחוד

נשנה את $F$ להיות:

F=(F_{1}\times Q_{2})\cup(Q_{1}\times F_{2})

באוטומט שבנינו, נוכל לשנות את זה לכך ש- $q_{0}p_{1}$ ו- $q_{1}p_{0}$ יהיו מצבים מקבלים בנוסף ל- $q_{0}p_{0}$ .

תרגול

תרגיל

נתונות שתי שפות $L_{1},L_{2}$ מעל אותו א"ב $\Sigma$ .
נגדיר שפה חדשה - שפת הריצ'רץ':

L_{zip}=\left\{ \sigma_{1}\gamma_{1}\dots\sigma_{n}\gamma_{n}|\sigma_{1},\dots,\sigma_{n}\in L_{1},\gamma_{1},\dots,\gamma_{n}\in L_{2} \right\}

הוכיחו כי אם $L_{1},L_{2}$ רגולריותף אז גם $L_{zip}$ רגולרית.

A_{i}=(Q_{i},\Sigma,q_{0}^i,\delta_{i},F_{i})

ומתקיים $L(A_{i})=L_{i}$ .
נגדיר אוטומט $A$ עבור $L_{zip}$ :

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

נגדיר $Q=Q_{1}\times Q_{2}\times \left\{ 1,2 \right\}$ .
נבחר $q_{0}=(q_{0}^1,q_{0}^2,1)$ .
לכל $\sigma \in\Sigma$ ולכל $q \in Q_{1},p \in Q_{2}$ :

\begin{matrix} \delta((q,p,1),\sigma)= (\delta_{1}(q,\sigma),p,2)\\ \delta((q,p,2),\sigma)=(q,\delta_{2}(p,\sigma),1) \end{matrix}

נגדיר את $F$ להיות:

F=F_{1}\times F_{2}\times \left\{ 1 \right\}

כעת, נוכיח את נכונות האוטומט.(כלומר, נוכיח כי $L(A)=L_{zip}$ )

∎

8 - אוטומט מכפלה

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

אוטומט מכפלה

8 - אוטומט מכפלה

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

אוטומט מכפלה

אוטומט מכפלה לחיתוך

אוטומט מכפלה לאיחוד

תרגול

אוטומט מכפלה לחיתוך

אוטומט מכפלה לאיחוד

תרגול