אוטומטים ושפות פורמליות/תכונות של שפות רגולריות/משפט מיהיל-נרוד: הבדלים בין גרסאות בדף

 

==רקע==

 

=== יחס שקילות ===

# סימטריות: אם a עומד ביחס עם b אזי גם b עומד ביחס עם a, כלומר <math>\ a\mathcal{R}b\Leftrightarrow b\mathcal{R}a</math>. לדוגמה: יחס האחווה "אח של" הוא סימטרי כי אם a אח של b אז גם b אח של a. לעומת זאת, יחס ההורות "a אב של b" איננו סימטרי.

# טרנזיטיביות: אם a נמצא ביחס ל-b ו-b נמצא באותו היחס ל-c אזי גם בין a ל-c מתקיים אותו היחס, ובניסוח פורמלי: <math>\ a\mathcal{R}b,b\mathcal{R}c\Rightarrow a\mathcal{R}c</math>. למשל, אם לסוס a צבע זהה לזה של סוס b, ול- b צבע זהה לשל c, אז ל- a אותו צבע כמו ל- c.