آلة خطية محدودة

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
الموسوعة الحرة

في علوم الحاسوب ، يعتبر الأوتومات الخطي المحدود (المختصر LBA ) شكلاً مقيدًا من آلة تورينج التي تعمل كنموذج أكثر دقة للحاسوب في العالم الحقيقي ، حيث أن تعريفها لا يفترض وجود شريط غير محدود.

من الناحية الرسمية، فإنه يستوفي الشروط الثلاثة التالية:

  • تتضمن أبجدية الإدخال الخاصة بها رمزين خاصين، يعملان كعلامات نهاية يسارية ويمينية.
  • قد لا تقوم انتقالاتها بطباعة رموز أخرى فوق علامات النهاية.
  • لا يجوز أن تتحرك انتقالاته إلى يسار علامة النهاية اليسرى ولا إلى يمين علامة النهاية اليمنى. [ 1 ] : 225

بمعنى آخر: بدلاً من وجود شريط لا نهائي محتمل لإجراء العمليات الحسابية عليه، فإن الحساب يقتصر على جزء الشريط الذي يحتوي على المدخلات بالإضافة إلى مربعي الشريط اللذين يحملان علامات النهاية.

أما التعريف البديل الأقل تقييداً فهو كالتالي:

  • مثل آلة تورينج ، يمتلك جهاز LBA شريطًا مكونًا من خلايا يمكن أن تحتوي على رموز من أبجدية محدودة ، ورأسًا يمكنه القراءة من أو الكتابة إلى خلية واحدة على الشريط في كل مرة ويمكن تحريكه، وعددًا محدودًا من الحالات.
  • تختلف آلة الأوتوماتا الخطية المحدودة (LBA) عن آلة تورينج في أن الشريط، على الرغم من اعتباره في البداية غير محدود الطول، لا يمكن الوصول إلا إلى جزء متصل محدود منه، طوله دالة خطية لطول المدخلات الأولية، بواسطة رأس القراءة/الكتابة؛ ومن هنا جاء اسم الأوتوماتا الخطية المحدودة . [ 1 ] : 225

يؤدي التعريف القوي والتعريف الأضعف إلى نفس القدرات الحسابية لفئات الأوتوماتون المعنية، [ 1 ] : 225 بنفس الحجة المستخدمة لإثبات نظرية التسريع الخطي .

اللغات الحساسة للسياق واللغات ذات الصلة بالسياق

تُعدّ الأوتوماتا الخطية المحدودة مُستقبِلات لفئة اللغات الحساسة للسياق . [ 1 ] : 225-226. القيد الوحيد المفروض على قواعد هذه اللغات هو عدم وجود قاعدة إنتاج تُحوّل سلسلة نصية إلى سلسلة أقصر. وبالتالي، لا يمكن لأي اشتقاق لسلسلة نصية في لغة حساسة للسياق أن يحتوي على صيغة جملية أطول من السلسلة نفسها. ولأن هناك تطابقًا تامًا بين الأوتوماتا الخطية المحدودة وهذه القواعد، فلا يلزم استخدام شريط أكثر من الشريط الذي تشغله السلسلة الأصلية لكي تتعرف الأوتوماتا على السلسلة.

تاريخ

في عام 1960، قدّم جون مايهيل نموذجًا للأتمتة يُعرف اليوم باسم الأتمتة الخطية المحدودة الحتمية. [ 2 ] وفي عام 1963، أثبت بيتر لاندويبر أن اللغات التي تقبلها الأتمتة الخطية المحدودة الحتمية حساسة للسياق. [ 3 ] وفي عام 1964، قدّم س. ي. كورودا النموذج الأكثر عمومية للأتمتة الخطية المحدودة (غير الحتمية)، وعدّل برهان لاندويبر ليُبيّن أن اللغات التي تقبلها الأتمتة الخطية المحدودة غير الحتمية هي تحديدًا اللغات الحساسة للسياق. [ 4 ] [ 5 ]

مشاكل LBA

في ورقته البحثية الرائدة، طرح كورودا تحديين بحثيين، عُرفا لاحقًا باسم "مشكلات LBA": تتمثل المشكلة الأولى في ما إذا كانت فئة اللغات التي يقبلها LBA تساوي فئة اللغات التي يقبلها LBA الحتمي. ويمكن صياغة هذه المشكلة بإيجاز بلغة نظرية التعقيد الحسابي على النحو التالي:

المسألة الأولى في LBA : هل NSPACE (O( n )) = DSPACE (O( n ))؟

تتمثل المشكلة الثانية في LBA فيما إذا كانت فئة اللغات المقبولة بواسطة LBA مغلقة تحت المكمل.

المسألة الثانية المتعلقة بـ LBA : هل NSPACE (O( n )) = co- NSPACE (O( n ))؟

كما لاحظ كورودا سابقًا، فإن الإجابة السلبية على مسألة LBA الثانية تستلزم إجابة سلبية على المسألة الأولى. لكن مسألة LBA الثانية لها إجابة إيجابية، وهو ما يُستنتج من نظرية إيمرمان-سيليبسيني التي أُثبتت بعد عشرين عامًا من طرح المسألة. [ 6 ] [ 7 ] وحتى اليوم، لا تزال مسألة LBA الأولى مفتوحة. تُقدم نظرية سافيتش رؤية أولية، وهي أن NSPACE (O( n )) ⊆ DSPACE (O( n² ) ). [ 8 ]

مراجع

  1. 1 2 3 4 هوبكروفت، جون إي .؛ أولمان، جيفري د. (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة (الطبعة الأولى  ). أديسون-ويسلي. ISBN 0-201-02988-X.( متاح للزبائن ذوي الإعاقات البصرية )
  2. ↑ جون مايهيل (يونيو 1960). الأوتوماتا الخطية المحدودة (مذكرة فنية من قسم تطوير الطيران). قاعدة رايت باترسون الجوية، قسم تطوير الطيران، أوهايو.
  3. ↑ بي إس لاندويبر (1963). "ثلاث نظريات حول قواعد بنية العبارة من النوع 1" . المعلومات والتحكم . 6 (2): 131-136 . doi : 10.1016/s0019-9958(63)90169-4 .
  4. ↑ سيج-يوكي كورودا (يونيو 1964). "فئات اللغات والآلات الخطية المحدودة" . المعلومات والتحكم . 7 (2): 207-223 . doi : 10.1016/s0019-9958(64)90120-2 .
  5. ↑ ويليم جيه إم ليفيلت (2008). مقدمة في نظرية اللغات الرسمية والأتمتة . دار نشر جون بنجامينز. الصفحات 126-127 . ISBN  978-90-272-3250-2.
  6. ↑ إيمرمان، نيل (1988)، "الفضاء غير الحتمي مغلق تحت التتميم" (ملف PDF) ، مجلة SIAM للحوسبة ، 17 (5): 935-938 ، doi : 10.1137/0217058 ، MR 0961049 
  7. ^ Szelepcsényi، Róbert (1988)، “طريقة التعداد القسري للآلات غير الحتمية”، Acta Informatica ، 26 (3): 279–284 ، دوى : 10.1007 / BF00299636 ، S2CID 10838178 
  8. ↑ أرورا، سانجيف ؛ باراك، بواز (2009). نظرية التعقيد: منهج حديث . مطبعة جامعة كامبريدج. ISBN 978-0-521-42426-4.