לדלג לתוכן

אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

בפרק זה נתאר מספר תכונות של שפות חסרות הקשר.
בדומה לשפות רגולריות, נתעניין בתכונות הסגור - אילו פעולות על שפות משמרות את היות השפה חסרת הקשר. להבדיל, משפות רגולריות, מספר פעולות ייצרו שפות שאינן חסרות הקשר. כמו כן, נדון בלמת ניפוח עבור שפות חסרות הקשר. נסיים בתכונות של דקדוקים - נראה שניתן להמיר כל דקדוק לצורה "נורמאלית" בה לכללי הגזירה נתונים יש צורה קבועה ופשוטה.



הפרק הקודם:
דקדוקים חסרי הקשר
תכונות של שפות חסרות הקשר הפרק הבא:
תכונות סגור