מידע על שפות

רדוקציות

רדוקציות חישוביות: העברת כריעות וזיהוי בין שפות.

היררכיית המחלקות

מקרא

RE — ניתנות למנייה רקורסיבית: שפות שמכונת טיורינג יכולה לזהות
CFL — חופשיות־הקשר: שפות ש־PDA או CFG יכולים לייצר
Regular — שפות ש־DFA, NFA או ביטוי רגולרי יכולים לזהות

כל טבעת מייצגת מחלקת שפות, כאשר הטבעות הפנימיות הן תת־קבוצות של הטבעות החיצוניות. למשל, כל השפות הרגולריות הן גם חופשיות־הקשר וגם ניתנות למנייה רקורסיבית, אך לא כל השפות חופשיות־ההקשר הן רגולריות. דוגמאות השפה ממחישות שפה השייכת לאותה מחלקה אך לא לאף תת־מחלקה. למשל, aⁿbⁿ היא חופשית־הקשר אך אינה רגולרית, בעוד ש־A_TM ניתנת למנייה רקורסיבית אך אינה חופשית־הקשר.

תכונות סגירות

פעולה	רגולרית	CFL	RE
איחוד	✓	✓	✓
חיתוך	✓	✗	✓
משלים	✓	✗	✗
שרשור	✓	✓	✓
כוכב קלין	✓	✓	✓
חיתוך עם רגולרית	✓	✓	✓
הומומורפיזם	✓	✓	✓
הומומורפיזם הפוך	✓	✓	✓
היפוך	✓	✓	✓
הפרש קבוצות	✓	✗	✗

CFL = חופשית־הקשר · RE = ניתנת למנייה רקורסיבית