الأوتومات المنتهي اللاحتمي

الأوتومات المنتهي اللاحتمي 

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

إن كلمة أتومات  نفسها مرتبطة بكلمة (automation) أتمتة ،  وتدل على العمليات التلقائية التي تتبع خلال انتاج عمليات محددة . 

يتمكن علماء الحاسوب من خلال الأتومات من فهم كيف تقوم الآلات القيام بالوظائف وحل المشكلات ، إن الهدف الرئيسي من نظرية الأتومات هي تطوير الطرق والأساليب التي تمكن علماء الحاسوب من وصف وتحليل السلوك الديناميكي للأنظمة المستقلة. 

يعتبر نموذج الأتومات المنتهي من أبسط النماذج للغات الصورية المفيدة، وقد صمم أصلا لنمذجة الدارات المنطقية التسلسلية وقد ازدادت أهميته لدى استخدامه في تصميم وتنفيذ لغات البرمجة، ومترجماتها ومعالجات النصوص.

 يوجد عدة أنواع من نماذج الأتومات المنتهي: 

• الأتومات المنتهي الحتمي 
• الأتومات المنتهي اللاحتمي 
• الأتومات المنتهي اللاحتمي مع تحرك إيبسلون 
• وبالرغم من وجود هذه النماذج من الأتومات المنتهي،  فإنها جميعا تعتبر ذات طاقة تعبيرية واحدة كما يوجد تكافؤ بين هذه النماذج  (Regular Language)  تستوعب ما يسمى بالغات النظامية 

وسنتكلم في هذا البحث عن الأتومات المنتهي اللاحتمي بشيء من التفصيل 

أولا : الاتومات المنتهي اللاحتمي (لمحة تاريخية والأهمية ) 

قدمت نظرية الأتومات المنتهي اللاحتمي من قبل العالمين الرياضيين مايكل أوسر رابين ودانا ستيوارت سكوت في العام  1959م ، والتي أظهرت تكافؤا مع الأتومات المنتهي الحتمي.

إن الأتومات المنتهي اللاحتمي هو عبارة عن آلة منتهية الحالات حيث يمكن في كل حالة وبوجود دخل معين أن ينتقل الأتومات لعدة حالات تالية ، أي من الممكن أن ننتقل لأكثر من حالة في الوقت ذاته. 

حيث يكفي وجود مسار واحد على الأقل يبقل من الحالة البدائية للحالة النهائية عند انتهاء الدخل وليس من الضروري وجود كل الرموز لأن بعضها يؤدي إلى موت المسار ، ويعتبر الأتومات المنتهي اللاحتمي أسهل في التعبير عن المسائل من الأتومات المنتهي الحتمي ، ويمكن دوما تحويل كل أتومات منتهي لاحتمي إلى أتومات منتهي حتمي . 

ولكي نستطيع فهم فكرة الأتومات المنتهي اللاحتمي يمكن أن نقوم بشرح مبسط :

•  لنتخيل أنه في الحياة عندما يكون عليك أن تختار تستطيع محاولة طريقين ممكنين o وتجربهما ، وفي النهاية تستطيع الرجوع غلى نقطة البداية لتقرر ايهما كان الاختيار الأفضل ، عندها تستطيع ان تقرر من ستتزوج ، وأي عمل ينبغي عليك أن تقبله، وذلك من خلال علمك بالنتائج المستقبلية من قبل خلال التجربة، هذه هي فكرة الأتومات المنتهي اللاحتمي . 

يستخدم هذا النوع من الأتومات في العديد من الحالات مثل المترجمات ومحركات البحث ، وكذلك للبحث عن نص محرفي معين 

 فتعود أهمية استخدامه إلى وضع قواعد ثابتة والسير عليها مما يؤدي لاختصار الكثير من الوقت وخصوصا في المترجمات حيث أول مرحلة في المترجمات هي التحليل النصي أو القواعدي حيث في السابق كانت هذه المرحلة تتم بشكل يدوي قبل استخدام الأتومات من خلال كتابة توابع بشكل يدوي للتعرف على كل كلمة من الكلمات المحجوزة مثلا ، أما باستخدام الأتومات المنتهي اللاحتمي أصبحنا نتعرف على الكلمات المحجوزة بشكل اسرع من خلال عدة مراحل يقوم بها الأتومات بشكل تلقائي. 

ثانيا: التصميم الرياضي والعلاقة باللغات الصورية : 

يعرف الأتومات بشكل رسمي كالتالي : 

الأتومات المنتهي اللاحتمي هو الخماسية المرتبة 

حيث : 

• اللغات الصورية : تعرف اللغات الصورية بأنها جميع اللغات التي نتعامل معها سواء اللغات الطبيعية ، أو لغات البرمجة التي نقوم باستخدامها لبناء برامجنا .

 تعتبر اللغات المنتظمة من أبسط انواع اللغات الصورية وتحوي :

1. الأتومات المنتهي الحتمي
2. الأتومات المنتهي اللاحتمي 
3. الأتومات المنتهي اللاحتمي مع التحويل إيبسلون 
4. التعابير المنظمة (regular expressions)

حيث تستخدم جميع هذه المفردات لتوصيف لغة منتظمة واحدة ، أي يمكن للغة منتظمة واحدة أن توصف بجميع النماذج الأربعة السابقة. 

إن اللغة المقبولة في الأتومات المنتهي اللاحتمي هي اللغة النظامية ، وتجدر الإشارة أنه توجد بعض اللغات التي لايمكن تقديمها عبر الأتومات المنهي الحتمي ، لكن يمكن تمثيلها عبر الأتومات المنتهي اللاحتمي ، أي ان الاتومات المنتهي اللاحتمي يقبل جميع اللغات التي يقبلها الأتومات المنتهي الحتمي . 

قبول سلسلة وقبول لغة: 

إن هذا الأتومات يقبل السلاسل التالية : abb,aabb.babb,aaabb

على سبيل المثال السلسلة aabb  مقبولة بواسطة المسار من الحالة  0 إلى الحالة  0  بسهم معنون ب . a و من ثم الى الحالة 2 بسهم معنون ب . b  و من ثم الى الحالة 3 بسهم معنون ب . b فالمسار يمثل بمتتالية من الانتقالات على الحالة تدعى تحركات ، كما يضح المخطط التالي :

التحركات الناتجة عن قبول السلسلة : aabb 

مثال يوضح قبول الأتومات المنتهي اللاحتمي والحتمي لنفس اللغة: 

ويوجد أيضا نمط مهم وهو الأتومات المنتهي اللاحتمي مع تحرك إيبسلون :  

ثالثا : التطبيقات :

كما هو معلوم فأن الأتومات المنتهي اللاحتمي والأتومات المنتهي الحتمي متكافئان ، ولذلك فإن أي لغة مقبولة من قبل الأتومات المنتهي اللاحتمي تكون مقبولة أيضا من الأتومات المنتهي الحتمي.

إن تأسيس مثل هذا التكافؤ له أهمية تطبيقية عالية في عدة حالات مختلفة كالحالات التالية : 

1. إن بناء الأتومات المنتهي اللاحتمي لتعريف لغة معطاه  هو في بعض الأحيان أسهل بكثير من بناء الاتومات المنتهي الحتمي لنفس اللغة . 
2.  يستخدم الأتومات المنتهي اللاحتمي  لتقليل تعقيد العمل الرياضي المطلوب لتأسيس خصائص مهمة في نظرية الاتمتة . 
3.  إن الأتومات المنتهي اللاحتمي يمكن تطبيقه بشكل جيد لإثبات خصائص الإغلاق للغات النظامية بطرق أسهل بكثير مقارنة بالأتومات المنتهي الحتمي. 

• إن الأتومات المنتهي اللاحتمي يمكننا من الانتقال من عملية إلى أخرى دون الحاجة لقراءة المدخلات وذلك عندما يوجد المتحول إيبسلون بين هاتين العمليتين 

 كيف نستطيع تطبيق الأتومات المنتهي اللاحتمي : 

1.  الأتومات المنتهي اللاحتمي يستطيع التنبؤ بالمسار الصحيح الذي يقود إلى حالة مقبولة 
2. الأتومات المنتهي اللاحتمي يبحث في كل المسارات خلال مخطط الحالة ليوجد هذا المسار الصحيح 
3. تعتبر الحالة الاولى المفضلة لدى التحليلات الرياضية ،  بينما الحالة الثانية هي مقاربة معقولة لتطبيق وتنفيذ الأتومات المنتهي اللاحتمي 

يظهر الشكل التالي الفرق الواضح بين الأتومات المنتهي الحتمي واللاحتمي لنفس اللغة التي تقبل تذكر آخر ثلاثة رموز: 

ويظهر الشكل التالي أتومات منتهي حتمي ولاحتمي بالنسبة للغة تقبل كل المسارات (A , B , C) والتي تنتهي بواحدة من  ab,bc,ca

رابعا : الامثلة : 

مثال 1 :

هذا الأتومات المنتهي اللاحتمي يقبل فقط المسارات التي تنتهي ب 01

قبول السلسلة 1100101

مثال 2 : 

ليكن لدينا الأوتومات المنتهي اللاحتمي التالي :

إن مجموعة القوة لهذه الحالة هي : 
  ¢ , {q0} , {q1} , {q2} , {q0,q1} , {q0,q2} , {q1,q2} , {q0,q1,q2} 


مثال 3 :
أوتومات منتهي لا حتمي مع إغلاق إبسيلون :

خامسا: خاتمة: 

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