في العصر التكنولوجي اليوم ، شهد كل من مجال الأجهزة والبرامج تطوراً هائلاً. شوهد أحد مجالات التطوير الرئيسية في أساليب تصميمات الأجهزة. مع ال التكنولوجيا المتنامية ، كان مفهوم الأجهزة - التصميم المشترك للبرامج ممكنًا للتنفيذ. يتم تطوير طرق مختلفة من خلالها ، باستخدام البرنامج يمكن للمرء تصميم ومحاكاة أنظمة الأجهزة بشكل كامل. إحدى هذه الطرق هي نظرية الأوتوماتا. نظرية الأوتوماتا هي فرع من علوم الكومبيوتر الذي يتعامل مع تصميم النموذج المجرد لأجهزة الحوسبة التي تتبع تسلسل الخطوات المحدد مسبقًا تلقائيًا. تتناول هذه المقالة معلومات موجزة عن البرنامج التعليمي لـ automata.

ما هي نظرية الأوتوماتا؟

كلمة Automata مشتقة من اليونانية ، والتي تعني 'العمل الذاتي'. إن Automaton هو نموذج رياضي للآلة. يتكون Automaton من حالات وانتقالات. نظرًا لأن المدخلات يتم تقديمها إلى التشغيل الآلي ، فإنها تقوم بالانتقال إلى الحالة التالية ، اعتمادًا على وظيفة الانتقال. مدخلات وظيفة الانتقال هي الحالة الحالية والرموز الحديثة. إذا كان لدى Automaton عدد محدود من الحالات ، فإنه يُعرف باسم Finite Automata أو آلة الدولة المحدودة . يتم تمثيل الأوتوماتا المنتهية بـ 5 مجموعات (Q ، ∑ ، δ ، qo ، F)

أين،

س = مجموعة محدودة من الحالات.

∑ = مجموعة محدودة من الرموز تسمى أيضًا أبجدية الأوتوماتا.

δ = وظيفة الانتقال.

qo = الحالة الأولية للإدخال.

F = مجموعة الحالات النهائية لـ Q.

المصطلحات الأساسية لنظرية الأوتوماتا

بعض المصطلحات الأساسية لنظرية الأوتوماتا هي-

1 . الأبجدية : أي مجموعة محدودة من الرموز في نظرية الأوتوماتا تُعرف بالأبجدية. يمثلها الحرف∑ المجموعة {أ ، ب ، ج ، د ، هـ ،} تسمى مجموعة الأبجدية ، بينما تسمى أحرف المجموعة 'أ' ، 'ب' ، 'ج' ، 'د' ، 'ه' حرف او رمز.

اثنين . خيط : في automata ، السلسلة عبارة عن تسلسل محدود من الرموز المأخوذة من مجموعة الأبجدية ∑ ، على سبيل المثال ، السلسلة S = 'adeaddadc' صالحة على مجموعة الأبجدية = {a، b، c، d، e،}

“ما هي بطاقة sims المستخدمة ”

3 . طول الخيط : يُعرف عدد الرموز الموجودة في السلسلة باسم طول السلسلة. بالنسبة للسلسلة S = 'adaada' ، يكون طول السلسلة | S | = 6. إذا كان طول السلسلة 0 ، فإنها تسمى سلسلة فارغة.

4 . كلين ستار : هو العامل الأحادي في مجموعة الرموز Σ ، والذي يعطي المجموعة اللانهائية من كل السلاسل الممكنة ، بما في ذلك λ ، لجميع الأطوال الممكنة على المجموعة Σ. يمثلها. على سبيل المثال ، للمجموعة Σ = {c، d}، ∑ * = {λ، c، d، cd، dc، cc، dd، ……}.

5 . إغلاق كلاين : هي المجموعة اللانهائية لجميع السلاسل الممكنة لمجموعة الأبجدية باستثناء λ. يتم الإشارة إليه بواسطة. للمجموعة Σ = {a، d}، ∑ + = {a، d، ad، da، aa، dd،… ..}.

6 . لغة : اللغة هي المجموعة الفرعية لمجموعة نجوم Kleene ∑ * لبعض مجموعات الأبجدية Σ. يمكن أن تكون اللغة محدودة أو غير محدودة. على سبيل المثال ، إذا كانت اللغة تأخذ كل السلاسل الممكنة ذات الطول 2 على المجموعة Σ = {a، d} ، إذن L = {aa، ad، da، dd}.

اللغات الرسمية والأوتوماتا

في نظرية الأوتوماتا ، اللغة الرسمية هي مجموعة من السلاسل ، حيث توجد كل سلسلة تتألف من رموز تنتمي إلى مجموعة الأبجدية المحدودة Σ. دعونا نفكر في لغة قطة ، والتي يمكن أن تحتوي على أي سلاسل من المجموعة اللانهائية أدناه ...
مواء!
ميو!
mewww !! ……

تم تعيين الأبجدية للغة القط Σ = {m، e، w،!}. دع هذه المجموعة تستخدم لـ Finite State Automata Model-m. ثم يتم الإشارة إلى اللغة الرسمية التي تتميز بالنموذج m بواسطة

L (م)
L (م) = {'mew!'، 'meww!'، 'mewww'، ……}

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

“دائرة التحكم عن بعد للأجهزة المنزلية ”

أوتوماتا محدودة حتمية

في النوع الحتمي من الأوتوماتا ، عندما يتم تقديم إدخال ، يمكننا دائمًا تحديد الحالة التي سيكون عليها الانتقال. نظرًا لأن هذا هو إنسان آلي محدود ، فإنه يُطلق عليه اسم أوتوماتيكي محدد محدد.

التمثيل الرسومي

مخطط الحالة هو الرسومات البيانية المستخدمة للتمثيل الرسومي للأوتوماتيكية المحددة المحددة. دعونا نفهم بمثال. دع الأتمتة المحدودة القطعية تكون ...
س = {أ ، ب ، ج ، د}.
Σ = {0 ، 1}
= {أ}
F = {د} وتكون وظيفة الانتقال

التمثيل البياني شكل جدول

الرسم التخطيطي للدولة

مخطط الدولة لأوتوماتا الحالة المحددة المحددة

من مخطط الدولة

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

آلية محدودة غير حتمية

تسمى الأوتوماتا التي لا يمكن فيها تحديد حالة المخرجات للمدخلات المحددة بـ Non-Deterministic Automata. يطلق عليه أيضًا اسم Non-Deterministic Finite Automata ، لأنه يحتوي على عدد محدود من الحالات. يتم تمثيل Finite Automata غير القطعي كمجموعة من 5 -tuple حيث (Q ، ∑ ، δ ، qo ، F)

س = مجموعة محدودة من الدول.
∑ = مجموعة الأبجدية.
δ = وظيفة الانتقال

أين : qo = الحالة الأولية.

التمثيل الرسومي

يتم تمثيل الآلات المحدودة غير الحتمية بمساعدة مخطط الحالة. دع الأوتوماتا المحدودة غير الحتمية تكون-

س = {أ ، ب ، ج ، د}
Σ = {0،1}
qo = {a}
F = {د}

التحولات

التمثيل البياني شكل جدول

“محرك تحريضي التيار المتردد أحادي الطور ”

الرسم التخطيطي للدولة

رسم تخطيطي للدولة للآليات المحدودة غير الحتمية

تطبيقات نظرية الأوتوماتا

تطبيقات نظرية الأوتوماتا تشمل ما يلي.

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

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