آلة تورينغ Turing machine: هي نموذج رياضي تجريدي يعبّر عن الأدا الوظيفي للحسابات المتتالية أو «الميكانيكية». صَمّم هذا النموذج آلان تورينغ Alan Turing للحصول على تعريف دقيق لمفهوم الخوارزمية أو»الإجرائية الميكانيكية». وما زال هذا النموذج الرياضي مستخدماً استخداماً واسعاً في علوم المعلوماتية النظرية، وخصوصاً عند حل المسائل ذات التعقيد الخوارزمي والحسابي المرتفعين.

"> آلة تورينغ Turing machine: هي نموذج رياضي تجريدي يعبّر عن الأدا الوظيفي للحسابات المتتالية أو «الميكانيكية». صَمّم هذا النموذج آلان تورينغ Alan Turing للحصول على تعريف دقيق لمفهوم الخوارزمية أو»الإجرائية الميكانيكية». وما زال هذا النموذج الرياضي مستخدماً استخداماً واسعاً في علوم المعلوماتية النظرية، وخصوصاً عند حل المسائل ذات التعقيد الخوارزمي والحسابي المرتفعين.

"/>

logo

logo

logo

logo

logo

الآلة المنتهية الحالات

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

Finite-state machine (FSM) - Machine à états finis(FSM)

 الآلة المنتهية الحالات

الآلة المنتهية الحالات

 الآلة المنتهية الحالات واللغات النظامية

 الآلة المنتهية الحالات ذات المكدس

 آلة تورينغ

الأوتومات الخلوي cellular automata

تطبيقات عملية

 

آلة تورينغ Turing machine: هي نموذج رياضي تجريدي يعبّر عن الأداء الوظيفي للحسابات المتتالية أو «الميكانيكية». صَمّم هذا النموذج آلان تورينغ Alan Turing للحصول على تعريف دقيق لمفهوم الخوارزمية أو»الإجرائية الميكانيكية». وما زال هذا النموذج الرياضي مستخدماً استخداماً واسعاً في علوم المعلوماتية النظرية، وخصوصاً عند حل المسائل ذات التعقيد الخوارزمي والحسابي المرتفعين.

تطوّر نموذج آلة تورينغ كثيراً عبر السنين، وانبثقت منه نماذج رياضية كثيرة، ومن أهم الأشكال المبسّطة هي الآلة المنتهية الحالات finite-state machine.

ما زال مفهوم الآلة المنتهية الحالات أساس علوم الحاسوب، ويُستخدم نموذجاً رياضياً في العديد من البرمجيات والعتاديات hardware، أهمها: برمجيات التصميم والتحقّق من أداء الدارات الرقمية، وبناء المحلِّل المفرداتي المستخدم في بناء المترجمات compiler لتعرّف مفردات اللغة ورموزها الخاصة بها، وبرمجيات استكشاف النصوص وصفحات الوب ومسحها للبحث عن كلمة أو البحث عن تعاقب عدة كلمات محدّدة، وأخيراً في برمجيات التحقّق من أداء الأنظمة التي تتمثل في عدد منتهٍ من الحالات مثل بروتوكولات الاتصالات أو بروتوكولات التبادل الآمن للمعلومات، ويُسمى هذا النموذج أحياناً بنموذج «الأوتومات» المنتهي finite automatum.

الآلة المنتهية الحالات واللغات النظامية:

للآلة المنتهية الحالات عدة أشكال متكافئة فيما بينها:

الآلة المنتهية الحالات الحتمية.

الآلة المنتهية الحالات اللاحتمية.

الآلة المنتهية الحالات اللاحتمية مع ε– تحرك (مع سلسلة فارغة).

تعبّر الآلة المنتهية الحالات عن صف واحد من اللغات التي تسمى اللغات النظاميةregular languages . ويمكن التعبير عن صف اللغات النظامية باستخدام التعابير النظاميةregular expressions.

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

تُعرَّف التعابير النظامية على الأبجدية S بالأسلوب العَودي recursive. وللتعابير الأشكال البسيطة التالية:

•  F هو التعبير النظامي الذي يرمّز اللغة الفارغة.

•   ε  هو التعبير النظامي الذي يرمّز اللغة ، وهي اللغة التي تحوي السلسلة الفارغة فقط.

  لكل رمز  ، فإن a هو تعبير منتظم يرمّز اللغة {a}.

ويمكن تعريف العمليات العودية الآتية على التعابير النظامية:

إذا كان r,s تعبيرين نظاميين يرمّزان اللغتين R,S على الترتيب فإن:

r+s هو التعبير النظامي الذي يرمّز اللغة RÈS.

r.s هو التعبير النظامي الذي يرمّز اللغة R.S.

r* هو التعبير النظامي الذي يرمّز اللغة R*.

يمكن استعمال الأقواس لإزالة أي غموض أو التباس في فهم التعبير النظامي، ويفُضّل عدم الإكثار من استخدامها والاعتماد على الأفضليات بين العمليات المذكورة آنفاً.

مثال:

يُراد نمذجة عمل جهاز لتوزيع المشروبات الغازية والعصائر، حيث يبلغ ثمن العلبة الواحدة 20 ليرة سورية، بافتراض أن الجهاز يقبل القطع النقدية (5، 10، 25)، ولا يعيد المبالغ المتبقية.

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

q0: الحالة الابتدائية.

q5: الحالة التي تمثل المبلغ 5 ليرات.

q10: الحالة التي تمثل المبلغ 10 ليرات.

q15: الحالة التي تمثل المبلغ 15 ليرة.

q20: الحالة النهائية التي تمثل المبلغ 20 ليرة فما فوق .

يمثّل الشكل (1) مخطط آلة منتهية الحالات حتمية لهذا الجهاز.

الشكل (1): آلة منتهية الحالات حتمية لتمثيل جهاز توزيع المشروبات الغازية.

الآلة المنتهية الحالات ذات المكدس:

تحتاج بعض اللغات غير النظامية إلى عدّاد لتعرّف عناصر هذه اللغة، بحيث تُخزّن قيمة العدّاد للدلالة على عدد مرات الظهور لرمز محدّد، ومقارنته بظهور رموز أخرى. ولتحقيق ذلك كان لا بدّ من إضافة مفهوم جديد إلى مفهوم الحالات المنتهية وآلية الانتقال، وهو مفهوم المكدس. والمكدس هو آلية تخزين منطقية تعمل بمبدأ الداخل أولاً والخارج آخراً first – in last – out (FILO) ويحتوي على كدسة من المعطيات. يستخدم كمجموعة من العناصر، وتسمى عملية حفظ المعطيات فيه بالدفع push أما عملية إزالة المعطيات منه فتسمى بالنبش pop. وعادة ما يرفق به مؤشر أو عداد يسمى مؤشر المكدّس Stack pointer.

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

مثال:

لتعرّف سلاسل اللغة ، وتتوفر خوارزميات تحويل يُعتمد جدول الانتقال transition اللاحتمي الآتي:

δ

0

1

ε

q0

Z

إضافة X

-

-

X

إضافة X

حذف قمة المكدس والانتقال إلى q1

-

q1

Z

-

-

حذف قمة المكدس

X

-

حذف قمة المكدس

-

حيث:

ε: التعبير النظامي الذي يرمز للغة الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image454986.jpg.

 z,x: بدء المكدّس start stack symbol.

q: الحالة State.

δ: الانتقال Transition.

يُلاحظ أن الحالة الابتدائية q0 توافق قراءة الأصفار وإضافة أطباق x بقدر يساوي عدد الأصفار المقروءة. أما الحالة q1 فإنها توافق قراءة الوحدان وحذف الأطباق x من المكدس. ويُلاحظ إذن إن سلاسل اللغة L تؤدي بالأوتومات إلى إفراغ المكدس، ومن ثمّ قبول هذه السلاسل.

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

آلة تورينغ:

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

يمكن تصميم آلة تورينغ بإنشاء العناصر التالية وتعريفها:

1. شريط Tape مؤلف من خانات متتالية، تحتوي هذه الخانات على رموز تنتمي إلى أبجدية منتهية. تضم الأبجدية رمزاً خاصاً يسمى فراغاً blank، ويُرمز له بـ ‘B’ أو ‘0’. وتضم رمزاً آخر أو عدة رموز أخرى. ومن المفترض أن يكون طول الشريط لا نهائياً من طرفه اليساري أو من طرفه اليميني. وبعبارات أخرى: يمكن لطول الشريط أن يكون بالقدر الذي تحتاج إليه آلة تورينغ للتنفيذ. تُعدّ الخانات التي لم تكتب آلة تورينغ عليها بعد أنها تحتوي على الرمز الفارغ.

2. رأس head متحرك يستطيع قراءة الرموز وكتابتها على الشريط، ويستطيع التحرك على الشريط باتجاه اليمين واليسار.

3. سجل الحالةstate register الذي يسجل الحالة الراهنة لآلة تورينغ، وعدد الحالات الممكنة دائماً منتهٍ. وثمة حالة خاصة، تسمى الحالة الابتدائية، وهي حالة الآلة قبل البدء بالتنفيذ.

4. لائحة التعليمات Instructions أو لائحة الانتقالات التي ترشد الآلة إلى الرمز الواجب كتابته، وطريقة الانتقال (‘L’ خانة لليسار،R’ خانة لليمين) وقيمة الحالة الجديدة، اعتماداً على الحالة الراهنة للآلة والرمز المقروء على الشريط. إذا لم تتوفر أي تعليمات - استناداً إلى الحالة الراهنة وإلى الرمز المقروء على الشريط- فذلك يعني توقف الآلة عن التنفيذ.

تعمل آلة تورينغ وفق المبادئ التالية:

1. يُهيأ شريط الخانات بسلسلة المحارف التي تشكّل معطيات الدخل.

2. يُوضع رأس الكتابة والقراءة على الخانة الأولى من الشريط، وتُسجل الحالة الابتدائية في سجل الحالة الراهنة.

3. ما دامت الثنائية (رمز حالي، حالة راهنة) واقعة في لائحة الانتقالات، تُنفّذ التعليمة الموافقة للثنائية من حيث انتقال الآلة إلى الحالة الجديدة وكتابة الرمز الجديد وتحريك رأس القراءة والكتابة بالاتجاه المحدّد في الانتقال.

4. إذا كانت الثنائية (رمز حالي، حالة راهنة) غير متوفرة في لائحة الانتقالات تتوقف الآلة، وتكون سلسلة الرموز المخزّنة في تلك اللحظة على الشريط هي ناتج المعالجة أو خرج الآلة.

استخدامات آلة تورينغ:

تقدمت بعض الأبحاث بفرضية أن بالإمكان حلّ أي مسألة حسابية معتمدة على إجرائية خوارزمية بآلة تورينغ. ولكن هذا الطرح لم يرقَ إلى مستوى النظرية الرياضية لأنه لا يفترض تعريفاً دقيقاً لمفهوم الإجرائيات الخوارزمية. وبالمقابل، يمكن تعريف مفهوم «الأنظمة القابلة للبرمجة» وإثبات أن قدرة هذه الأنظمة تكافئ قدرة آلات تورينغ.

يتيح مفهوم آلة تورينغ تصنيف المسائل الرياضية إلى ما يلي:

المسائل القابلة للحساب، وهي المسائل التي يمكن حلها باستخدام آلة تورينغ.

المسائل غير القابلة للحساب، مثل مسألة توقف آلة تورينغ.

المسائل ذات درجة التعقيد P، أي المسائل الممكن حلّها باستخدام آلة تورينغ خلال زمن كثير الحدود. وهي المسائل الوحيدة التي لها حل ناجع حاسوبياً.

المسائل ذات درجة تعقيد N-P (لا حتمية في زمن كثير حدود) أي المسائل التي يمكن حلها باستخدام آلة تورينغ اللاحتمية.

تعميم آلة تورينغ:

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

آلة تورينغ والآلة المنتهية الحالات:

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

تُعدّ الآلة المنتهية الحالات محدودة القدرات مقارنةً بآلة تورينغ، إذ تعجز الآلة المنتهية الحالات مثلاً عن تحديد كون سلسلة الدخل تحتوي على عدد أولي من الرموز أو لا، وتعجز الآلة المنتهية الحالات أيضاً عن تعرّف لغات بسيطة، فلا تميّز السلاسل المتوازنة من الأقواس المفتوحة والمغلقة من السلاسل غير المتوازنة.

ومن جهة أخرى يمكن النظر إلى الآلة المنتهية الحالات على أنها آلة تورينغ بعد فصل نصف شريط الدخل عن نصف شريط الخرج، كما هو موضح في الشكل (2).

الوصف: D:\المجلد 3 تقانة اخراج\316\29-2.jpg

الشكل (2): شريط باتجاه وحيد

الأوتومات الخلوي cellular automata:

الأوتومات الخلوي هو نموذج حسابي لا مركزي، يشكّل بنية تحتية لإنجاز حسابات بالغة التعقيد بالاستعانة بمعلومات محلية ذات درجة عالية من الفعالية والدقة. استخدم الباحثون مفاهيم التحكم اللامركزي والحسابات العامة في نمذجة العديد من التطبيقات المتعلقة بالعلوم الطبيعية، والرياضيات وعلوم الحاسوب. واستُخدمت هذه النماذج في تمثيل بعض الظواهر البيولوجية،والفيزيائية، مثل تدفق السوائل، وتشكل المجرات والهزات الأرضية.

يتكون الأوتومات الخلوي من مركّبتين، الأولى: هي شبكة من n خلية (كل خلية تمثل آلة منتهية الحالة)، وتترابط الخلايا بعضها ببعض وفق علاقة جوار محدّدة بغية تعريف سلاسل الدخل والخرج، مع فرض شروط حدية في حالة الشبكة المنتهية من الخلايا. فإذا كانت Σ مجموعة حالات الآلة المنتهية في كل خلية، والوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image541.jpg يشير إلى عدد الحالات في كل خلية فإن (t)iS يدل على حالة الخلية i في اللحظة t (حيث الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image548.jpg). وتشكّل حالة الخلية i مع حالات الخلايا المجاورة لها شعاعاً الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image556.jpgيُسمى جوار الخلية i في اللحظة t.

تشكّل المركّبة الثانية للأوتومات الخلوي قاعدة الانتقال أو تابع الانتقال الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image487126.jpgالذي يعرّف الحالة الجديدة للخلية i في اللحظة t+1، أي:الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image492957.jpg.

في كل أوتومات خلوي، تتوفر إشارة ساعة تزوّد الخلايا بلحظة التحديث، أي في كل خطوة زمنية تقوم جميع الخلايا وفي لحظة متزامنة بتحديث الحالة الراهنة باستخدام تابع الانتقال.

مثال: الأوتومات الخلوي الأحادي البعد:

في هذا الأوتومات لكل خلية حالتان الوصف: الوصف: الوصف: D:\المجلد 3 تقانة اخراج\316\Image497274.jpg،k=2 كما هو موضح في الشكل (3).

الوصف: D:\المجلد 3 تقانة اخراج\316\29-3.jpg

الشكل (3): أوتومات خلوي أحادي البعد

جدول الانتقال Φ:

الجوار

111

110

101

100

011

010

001

000

الخرج

0

1

1

0

1

1

1

0

مصفوفة الخلايا (جوار الخلايا الحدية بشكل دوري):

يتألف جوار كل خلية من الخلية نفسها ومن أقرب خليتين مجاورتين لها، مع شروط دورية للخلايا الحدودية، أي إن الخلية الأولى تنتمي إلى جوار الخلية الأخيرة وبالعكس. يُلاحظ أن جوار الخلية i هي ثلاثية من الرموز {0,1}.

أثبت الباحثون أنه من الممكن صياغة الأوتومات الخلوي بحيث يستطيع إنجاز حسابات معقدة ومحاكاة آلة تورينغ بشكلها العام.

تطبيقات عملية:

1) بناء المترجمات:

يُقصد بالمترجم كل مكوّن برمجي يسمح بتحويل مجموعة من التعليمات المكتوبة بلغة برمجية محدّدة إلى تعليمات لغة برمجية أخرى (مثال: عدة تعليمات تنفيذية بلغة الآلة). ومن جملة المهمات الواجب على المترجم القيام بها تعرّف تسلسل المحارف التي تشكّل الكلمات المفتاحية الخاصة باللغة البرمجية، وأسماء المتغيّرات، والثوابت الرقمية والنصيّة. وتُسمى هذه المرحلة بالتحليل المفرداتي. يُدخِل المستخدم هذه السلاسل على نحو تعاقب منتهٍ من محارف لوحة المفاتيح. وينبغي تمييز مختلف سلاسل الرموز بعضها من بعض، وهذا ما يسمح بتجزئة نص البرنامج وتقطيعه إلى ما يشبه جريان المحارف في وحدات.

أما المهمة الثانية فهي اكتشاف الأخطاء القواعدية. ولتحقيق ذلك يجب تعرّف سلاسل منتهية من الرموز المفرداتية التي فرزها التحليل المفرداتي (كلمة مفتاحية، أو متحول، أو ثابت، ...) إضافةً إلى عدد من رموز العمليات (+ ، - ، _ ، : ، ... )، ومن الرموز المساعدة ( } ، { ، ...). تشكّل هذه السلاسل من المفردات برنامجاً صحيحاً من الناحية القواعدية. يهتم التحليل القواعدي خاصةً بالتحقق من أن التعابير الحسابية مكتوبة كتابةً سليمة، وأن التعليمات والكتل البرمجية تتوافق والنماذج المصرّح عنها.

2) المعلوماتية الحيوية:

تعدّ البيولوجيا الجزيئية والجينية أمثلة طبيعية عن أغراض قابلة للنمذجة على نحو سلاسل خطية من الرموز (رموز أبجدية منتهية). إذ يحمل كل صبغيّ chromosome جميع المعلومات الجينية على شكل سلسلتين مجدولتين من الدنا DNA. وتُعدّ كل سلسلة تعاقباً من النوكليوتيدات nucleotides. ويتألف النوكليوتيد من حمض فسفوري، وسكر، ومن أساس آزوتي، يمكن توفره بإحدى القواعد الأربع G،C،T،A. تشكّل المعلومات المشفّرة في هذه الأسس جزءاً مهماً من كامل المعلومات الجينية. ومن ثمّ يمكن نمذجة السلسلة DNA على أنها سلسلة خطية معرّفة على الأبجدية المؤلفة من الأسس الأربعة {A,T,C,G}. ويمكن عندئذٍ البحث عن تعاقب معين من النوكليوتيدات في صبغيّ ما، أو اكتشاف التشابه أو الاختلاف بين جزأين من السلسلة. ويمكن لهذه التشابهات الجينية أن تكون مفيدة في معرفة التقاربات التطورية بين الشعوب أو تحديد بعض الجينات التي تحمل الوظائف نفسها، ولكن في جنسين مختلفين ومتقاربين، أو حتى تحديد درجة التقارب العائلي بين الأفراد. لا يقتصر هذا النوع من الحسابات على الجينات، وإنما يمكن تطبيقه على البروتينات. إذ يمكن نمذجة البنية الأولية للبروتينات على أنها تعاقب خطي من الأحماض الأمينية، أي يمكن نمذجة البروتينات على أنها سلاسل منتهية من رموز أبجدية مؤلفة من 20 حرفاً.

3) اللغات الطبيعية:

يُقصد باللغات الطبيعية اللغات المحكية (وهي أحياناً اللغات المكتوبة). تتوزّع اللغات الإنسانية على عدة مستويات في أنظمة من الأبجديات:

أنظمة المقاطع الصوتية: يمكن عدّ كل تعاقب سلس من المقاطع الصوتية سلسلةً خطية أحادية البعد من رموز أبجدية منتهية (وهي كل المقاطع الصوتية المستعملة). ولا تشكّل بداهةً كل سلسلة من المقاطع الصوتية عبارة مقبولة أو عبارة مفهومة.

أنظمة الكتابة: تستخدم هذه الأنظمة عموماً أبجدية منتهية من الرموز (الأبجديات المعروفة). وتسمح هذه الأبجديات ببناء الكلمات على نحو تعاقب خطي من الرموز. ولا يشكّل طبعاً كلّ تعاقب من الرموز كلمة مقبولة أو مفهومة. فالكلمات المقبولة هي الكلمات المذكورة في القواميس والمعاجم اللغوية.

أنظمة القواميس: بافتراض أن كلمات القاموس هي أبجدية منتهية، فإن كل العبارات اللغوية المعروفة هي تعاقب كلمات من هذه الأبجدية. ولكن ليست كل عبارة مكوّنة من كلمات الأبجدية مقبولة (صحيحة القواعد) أو مفهومة وذات دلالة.

يتوفر العديد من مسائل معالجة اللغات الطبيعية التي يمكن نمذجتها على نحو مسائل في نظرية اللغات. كما يعود فضل التطوّر العلمي في العديد من نواحي نظرية اللغات إلى اللغويين الصوريين.

تمثل الآلة المنتهية الحالات أداة قوية ومعبّرة لبناء منطق التحكم وتوصيفه للكثير من التطبيقات. وهي مستخدمة على نطاق واسع لبناء بروتوكولات الاتصالات، وللتحكم في بناء التطبيقات التفاعلية(GUI) graphic user interfac، وفي الكثير من التطبيقات المشابهة. وهي تقدّم تمثيلاً بيانياً مركّزاً، إذ يُمثّل الكثير من المنطق بمخطط صغير نسبياً. وتعود أسباب قوة التمثيل إلى اتباع القليل من القواعد، وإلى سهولة التحقق من صحة التمثيل، وإلى القدرة على توليد رماز برمجي آلياً يُترجِم المنطق المضمّن في الآلة المنتهية الحالات.

أيمن حمادة

مراجع للاستزادة:

- M. P. Béal and M. Crochemore, Minimizing Local Automata Information Theory, ISIT 2007. IEEE International Symposium on, 2007.

- A. Deutsch and S. Dormann. Cellular Automaton Modeling of Biological Pattern Formation, Birkh Auser Boston Inc., 2003.

- M. Mohri, F. C. N. Pereira, and M. Riley, Weighted Finite - State Transducers in Speech Recognition, Computer Speech and Language, 16(1):69 - 88, 2002.

- F. Wagner, R. Schmuki, T. Wagner, P. Wolstenholme, Modeling Software with Finite State Machines: A Practical Approach, Auerbach Publications, CRC Press Taylor & Francis Group, 2006.

 


التصنيف : هندسة الحواسيب
النوع : هندسة الحواسيب
المجلد: المجلد الثالث
رقم الصفحة ضمن المجلد :
مشاركة :

اترك تعليقك



آخر أخبار الهيئة :

البحوث الأكثر قراءة

هل تعلم ؟؟

عدد الزوار حاليا : 14
الكل : 9057446
اليوم : 676