الآلات ذاتية الحركة واللغات الشكلية
تدرس نظرية الآلات ذاتية الحركة واللغات الشكلية الآلات المثالية ذات القوة المتزايدة وفئات السلاسل، أو اللغات، التي يمكن لكل منها التعرف عليها، مما يوفر وصفًا رياضيًا دقيقًا لما يُعد نمطًا وما يتطلبه اكتشافه.
Definition
اللغة الشكلية هي مجموعة من السلاسل المحدودة على أبجدية ثابتة، والآلة ذاتية الحركة هي جهاز حاسوبي تجريدي تُعرّف حساباته المقبولة مثل هذه اللغة؛ وتصنف هذه المنطقة اللغات حسب أبسط نوع من الآلات ذاتية الحركة أو القواعد التي تولدها أو تتعرف عليها.
Scope
تغطي هذه المنطقة الآلات ذاتية الحركة المحدودة واللغات المنتظمة، والآلات ذات الذاكرة المكدسة واللغات الخالية من السياق، وتسلسل تشومسكي الهرمي الذي يربط القواعد بنماذج الآلات، وخصائص الإغلاق والتقرير لفئات اللغات، والآلات ذاتية الحركة التي تعالج الكلمات والأشجار اللانهائية، بالإضافة إلى التوصيفات الجبرية والمنطقية المصاحبة لها.
Sub-topics
Core questions
- ما هي اللغات التي يمكن لآلة ذات ذاكرة محدودة التعرف عليها، وما الذي لا يمكنها التعرف عليه؟
- كيف تتوافق القواعد ونماذج الآلات عبر مستويات تسلسل تشومسكي الهرمي؟
- ما هي الأسئلة المتعلقة بفئة لغوية، مثل الخلو أو التكافؤ، التي يمكن تحديدها خوارزميًا؟
- كيف تمتد الآلات ذاتية الحركة إلى الكلمات والأشجار اللانهائية، ولماذا يهم هذا للتحقق؟
Key theories
- تكافؤ الآلات ذاتية الحركة المحدودة الحتمية وغير الحتمية
- يمكن تحويل كل آلة ذاتية حركة محدودة غير حتمية عن طريق بناء المجموعات الفرعية إلى آلة حتمية تقبل نفس اللغة، لذا فإن عدم الحتمية لا تضيف قوة تعرفية على مستوى الحالة المحدودة على الرغم من أنها قد تكون أكثر إيجازًا بشكل كبير.
- نظرية كليني
- اللغات التي تتعرف عليها الآلات ذاتية الحركة المحدودة هي بالضبط اللغات المنتظمة الموصوفة بالتعبيرات المنتظمة، مما يربط بين وجهات النظر الآلية والجبرية والنحوية لأبسط فئة لغوية.
- تسلسل تشومسكي الهرمي
- تشكل اللغات المنتظمة، والخالية من السياق، والحساسة للسياق، والقابلة للتعداد بشكل تكراري سلسلة احتواء صارمة، حيث يتطابق كل مستوى مع نوع قواعد ونموذج آلة ذات بنية ذاكرة مقابلة.
Clinical relevance
تُستخدم الآلات ذاتية الحركة المحدودة والتعبيرات المنتظمة في التحليل المعجمي في المترجمات، والبحث النصي، وتحديد البروتوكولات، بينما تشكل القواعد الخالية من السياق أساس تحليل لغات البرمجة؛ وتشكل الآلات ذاتية الحركة على الكائنات اللانهائية جوهر الخوارزميات في التحقق من النماذج، حيث يتم التحقق من نظام ما مقابل مواصفات منطقية زمنية.
History
نشأت نماذج الحالات المحدودة من الشبكات العصبية لمكولوتش وبيتس في الأربعينيات من القرن الماضي، وأعطاها كليني شكلًا نظريًا للغة حوالي عام 1951. قدم رابين وسكوت الآلات ذاتية الحركة غير الحتمية في عام 1959، بينما نظمت قواعد تشومسكي من أواخر الخمسينيات فئات اللغات في التسلسل الهرمي الذي لا يزال يشكل بنية الموضوع.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- لماذا لا تستطيع الآلة ذاتية الحركة المحدودة التعرف على الأقواس المتوازنة؟
- يتطلب التعرف على التداخل العميق بشكل تعسفي عدّ عدد الفتحات التي لا تزال غير متطابقة، وهو ما يمكن أن يتجاوز أي عدد ثابت من الحالات. تمتلك الآلة ذاتية الحركة المحدودة ذاكرة محدودة فقط، لذا فإن قدرة العد هذه تقع على مستوى أعلى، مع الآلات ذات الذاكرة المكدسة واللغات الخالية من السياق.
- ما هي الفائدة العملية لنظرية اللغة الشكلية؟
- تخبر المهندسين بالأنماط التي يمكن لأداة معينة التعبير عنها. التعبيرات المنتظمة كافية للرموز ولكن ليس للبنية المتداخلة، وهذا هو السبب في أن المترجمات تقسم العمل بين محلل معجمي منتظم ومحلل خالي من السياق، ولماذا تعتمد أدوات التحقق على الآلات ذاتية الحركة على الكلمات اللانهائية.