نظرية اللغة الصورية والأتمتة
نظرية اللغات الصورية والآلات المجردة التي تتعرف عليها، وتوفر المفردات لوصف مدى تعقيد النمط اللغوي والخوارزميات التي يمكنها معالجته.
Definition
تدرس نظرية اللغة الصورية مجموعات السلاسل المعرفة بواسطة القواعد النحوية، وتدرس نظرية الأتمتة الآلات المجردة التي تقرر العضوية في تلك المجموعات.
Scope
تغطي تسلسل تشومسكي الهرمي (اللغات المنتظمة، الخالية من السياق، الحساسة للسياق، القابلة للعد تكراريًا)، والقواعد النحوية المقابلة، والآلات ذاتية التشغيل التي تتعرف عليها — آلات الحالات المحدودة، وآلات الدفع للأسفل، وآلات تورينج. وتتناول خصائص الإغلاق والقابلية للتقرير ذات الصلة بمعالجة اللغة ومسألة موقع اللغة الطبيعية في التسلسل الهرمي. وتُعامل مبرهنات الضخ (pumping lemmas) وإثباتات التعقيد الكاملة كخلفية وليست محتوى أساسيًا.
Core questions
- ما هي الآلة ذاتية التشغيل التي تتوافق مع كل مستوى من مستويات تسلسل تشومسكي الهرمي؟
- أين تقع اللغة الطبيعية في التسلسل الهرمي، ولماذا يُقال إنها تتجاوز قوة اللغات الخالية من السياق؟
- ماذا يعني أن تكون فئة لغوية مغلقة تحت عملية ما، ولماذا يهم ذلك في الهندسة؟
Key concepts
- لغة منتظمة
- قواعد نحوية خالية من السياق
- قواعد نحوية حساسة للسياق
- آلة ذات حالات محدودة
- آلة دفع للأسفل
- آلة تورينج
- خصائص الإغلاق
- حساسية السياق المعتدلة
Key theories
- تسلسل تشومسكي الهرمي
- أربع فئات متداخلة من اللغات الصورية، كل منها يتم إنشاؤها بواسطة نوع قواعد نحوية مقيد ويتم التعرف عليها بواسطة آلة ذاتية التشغيل مقابلة، وترتب التراكيب اللغوية حسب القوة الحسابية المطلوبة.
- التطابق بين القواعد النحوية والآلات ذاتية التشغيل
- كل فئة قواعد نحوية مكافئة بشكل مثبت لفئة آلات — القواعد النحوية المنتظمة للآلات ذات الحالات المحدودة، والقواعد النحوية الخالية من السياق لآلات الدفع للأسفل — مما يربط الأوصاف التوليدية بخوارزميات التعرف.
History
قدمت ورقة تشومسكي عام 1956 التسلسل الهرمي كجزء من حجة مفادها أن نماذج الحالات المحدودة غير كافية للغة الطبيعية. وقد أضفت العقود اللاحقة طابعًا رسميًا على مراسلات الأتمتة، وأظهر اللغويون الحاسوبيون لاحقًا أن اللغة الطبيعية تتطلب على الأكثر قوة 'حساسة للسياق بشكل معتدل'، مما حفز صياغات نحوية تتجاوز اللغات الخالية من السياق.
Debates
- هل اللغة الطبيعية خالية من السياق؟
- استُخدمت التبعيات المتقاطعة (cross-serial dependencies) في لغات مثل الألمانية السويسرية للقول بأن اللغة الطبيعية تتجاوز قوة اللغات الخالية من السياق، مما أدى إلى مفهوم حساسية السياق المعتدلة كمستوى مناسب للتعبيرية.
Key figures
- Noam Chomsky
- John Hopcroft
- Jeffrey Ullman
- Stephen Kleene
Related topics
Seminal works
- chomsky1956
- hopcroft2006
Frequently asked questions
- ما الفرق بين اللغة المنتظمة واللغة الخالية من السياق؟
- يمكن التعرف على اللغات المنتظمة بذاكرة محدودة بواسطة آلة ذات حالات محدودة؛ قد تتطلب اللغات الخالية من السياق مكدسًا (آلة دفع للأسفل) لتتبع البنية المتداخلة، مثل الأقواس المتوازنة أو الجمل الفرعية المضمنة.