Loading AI tools
מיון משפחות של דקדוקים על פי כללי השכתוב שהם מתירים מוויקיפדיה, האנציקלופדיה החופשית
ההיררכיה של חומסקי, היא מיון משפחות של דקדוקים על פי כללי השכתוב שהם מתירים. ההיררכיה נקראת על שם נועם חומסקי, שהיה הראשון אשר ניסה למיין משפחות דקדוקים לפי כוחם היחסי.
ההיררכיה שחומסקי הציע מסווגת דקדוקים פורמליים לקבוצות שונות על פי כוח הבעה עולה. כלומר, כל קבוצה עוקבת יכולה ליצור מערך רחב יותר של שפות פורמליות מזו שקדמה לה. לטענת חומסקי, מודליזציה של הבטים מסוימים בשפה טבעית דורשת דקדוק פורמלי מורכב יותר (כפי שהוא נמדד בהיררכיית חומסקי) מאשר מודליזציה של שפות אחרות. לדוגמה, בזמן ששפה רגולרית חזקה מספיק לתאר מורפולוגיה אנגלית, היא אינה חזקה מספיק כדי לתאר תחביר אנגלי. בנוסף להיותה רלוונטית לבלשנות, יש להיררכיית חומסקי שימוש במדעי המחשב, ויש לה קשרים חשובים גם לתורת האוטומטים.
באופן כללי, כל משפחה מתקבלת על ידי הוספת אילוץ על כללי השכתוב של המשפחה הקודמת, ועל-כן יש יחס של הכלה בין קבוצות הדקדוקים.
כמו כן, כל משפחה מתאימה למשפחת אוטומטים מטיפוס מסוים. כלומר, יש שקילות בין קבוצת השפות שנוצרות על ידי דקדוקים ממשפחה מסוימת לבין קבוצות השפות המתקבלות על ידי אוטומטים מהמשפחה המתאימה.
המיון מתחלק ל-4 טיפוסי משפחות:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.