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

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

Combinational logicFinite-state machinePushdown automatonTuring machineAutomata theory
أنواع الأوتوماتا
تبدأ الآلة الموصوفة في مخطط الحالة هذا من الحالة S1 ، وتنتقل بين الحالات باتباع الأسهم التي تحمل الرقم 0 أو 1 وفقًا لرموز الإدخال عند وصولها. تشير الدائرة المزدوجة إلى أن S1 حالة استقبال. وبما أن جميع المسارات من S1 إلى نفسها تحتوي على عدد زوجي من الأسهم التي تحمل الرقم 0، فإن هذه الآلة تقبل السلاسل النصية التي تحتوي على عدد زوجي من الأصفار.

نظرية الأوتوماتا هي دراسة الآلات المجردة والأوتوماتا ، بالإضافة إلى المشكلات الحسابية التي يمكن حلها باستخدامها. وهي نظرية في علوم الحاسوب النظرية، ترتبط ارتباطًا وثيقًا بالعلوم المعرفية والمنطق الرياضي . كلمة "أوتوماتا" مشتقة من الكلمة اليونانية αὐτόματος، والتي تعني "ذاتي الفعل، ذاتي الإرادة، ذاتي الحركة". الأوتوماتا (أو الأوتوماتا بصيغة الجمع) هي جهاز حاسوبي مجرد ذاتي الحركة ، يتبع تسلسلًا محددًا مسبقًا من العمليات تلقائيًا. يُطلق على الأوتوماتا ذات عدد محدود من الحالات اسم الأوتوماتا المحدودة (FA) أو آلة الحالة المحدودة (FSM). يوضح الشكل على اليمين آلة الحالة المحدودة، وهي نوع معروف من الأوتوماتا. تتكون هذه الأوتوماتا من حالات (ممثلة في الشكل بدوائر) وانتقالات (ممثلة بأسهم). عندما ترى الآلة رمزًا للإدخال، فإنها تقوم بانتقال (أو قفزة) إلى حالة أخرى، وفقًا لوظيفة الانتقال الخاصة بها ، والتي تأخذ الحالة السابقة ورمز الإدخال الحالي كمعاملات لها .

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

تاريخ

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

شهد عام 1956 نشر كتاب " دراسات الأوتوماتا" ، الذي جمع أعمال علماء من بينهم كلود شانون ، و. روس آشبي ، وجون فون نيومان ، ومارفن مينسكي ، وإدوارد ف. مور ، وستيفن كول كلين . [ 4 ] ومع نشر هذا المجلد، "برزت نظرية الأوتوماتا كتخصص مستقل نسبيًا". [ 5 ] تضمن الكتاب وصف كلين لمجموعة الأحداث المنتظمة، أو اللغات المنتظمة ، ومقياسًا مستقرًا نسبيًا للتعقيد في برامج آلة تورينج من قِبل شانون. [ 6 ] في العام نفسه، وصف نعوم تشومسكي التسلسل الهرمي لتشومسكي ، وهو عبارة عن تطابق بين الأوتوماتا والقواعد النحوية الرسمية ، [ 7 ] ونشر روس آشبي كتاب "مقدمة في علم التحكم الآلي" ، وهو كتاب مدرسي سهل الفهم يشرح الأوتوماتا والمعلومات باستخدام نظرية المجموعات الأساسية .

أدت دراسة الأوتوماتا الخطية المحدودة إلى نظرية مايهيل-نيرود [ 8 ] ، التي تُقدّم شرطًا ضروريًا وكافيًا لانتظام اللغة الرسمية، وعددًا دقيقًا لحالات الآلة الدنيا لتلك اللغة. وقد برهن مايكل أو. رابين ودانا سكوت في هذه الفترة على نظرية الضخ للغات المنتظمة ، وهي مفيدة أيضًا في براهين الانتظام، إلى جانب إثبات التكافؤ الحسابي للأوتوماتا المحدودة الحتمية وغير الحتمية [ 9 ] .

في ستينيات القرن العشرين، ظهرت مجموعة من النتائج الجبرية تُعرف باسم "نظرية البنية" أو "نظرية التفكيك الجبري"، والتي تناولت إمكانية إنشاء آلات متسلسلة من آلات أصغر حجمًا عن طريق الربط البيني. [ 10 ] وبينما يمكن محاكاة أي آلة ذاتية محدودة باستخدام مجموعة بوابات عامة ، فإن هذا يتطلب أن تحتوي دائرة المحاكاة على حلقات ذات تعقيد عشوائي. وتتناول نظرية البنية إمكانية إنشاء الآلات دون حلقات. [ 5 ] كما تبلورت نظرية التعقيد الحسابي في ستينيات القرن العشرين. [ 11 ] [ 12 ] وبحلول نهاية العقد، أصبحت نظرية الآلات الذاتية تُعتبر "الرياضيات البحتة لعلوم الحاسوب". [ 5 ]

الأوتوماتا

فيما يلي تعريف عام للآلة، والذي يقيد التعريف الأوسع للنظام إلى نظام يُنظر إليه على أنه يعمل في خطوات زمنية منفصلة، ​​حيث يتم تحديد سلوك حالته ومخرجاته في كل خطوة بواسطة وظائف ثابتة لحالته ومدخلاته فقط. [ 5 ]

وصف غير رسمي

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

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

التعريف الرسمي

آلة
يمكن تمثيل الآلة بشكل رسمي بواسطة مجموعة خماسيةم=⟨Σ،Γ،سؤال،دلتا،λ⟩{\displaystyle M=\langle \Sigma ,\Gamma ,Q,\delta ,\lambda \rangle }، أين:
  • Σ{\displaystyle \Sigma }هي مجموعة محدودة من الرموز ، تسمى أبجدية الإدخال الخاصة بالآلة،
  • Γ{\displaystyle \Gamma }وهي مجموعة أخرى محدودة من الرموز، تسمى أبجدية الإخراج الخاصة بالآلة،
  • سؤال{\displaystyle Q}هي مجموعة من الحالات ،
  • دلتا{\displaystyle \delta }هي دالة الحالة التالية أو دالة الانتقالدلتا:سؤال×Σ→سؤال{\displaystyle \delta :Q\times \Sigma \to Q}ربط أزواج الحالة والمدخلات بالحالات اللاحقة،
  • λ{\displaystyle \lambda }هي دالة الإخراج التاليةλ:سؤال×Σ→Γ{\displaystyle \lambda :Q\times \Sigma \to \Gamma }ربط أزواج الحالة والمدخلات بالمخرجات.
لوسؤال{\displaystyle Q}إذا كانت محدودة،م{\displaystyle M}هو آلة محدودة . [ 5 ]
أدخل الكلمة
تقرأ الآلة سلسلة محدودة من الرموزأ1أ2...أن{\displaystyle a_{1}a_{2}...a_{n}}، أينأأنا∈Σ{\displaystyle a_{i}\in \Sigma }، والتي تسمى كلمة الإدخال . ويُرمز إلى مجموعة جميع الكلمات بـΣ*{\displaystyle \Sigma ^{*}}.
يجري
سلسلة من الحالاتq0،q1،...،qن{\displaystyle q_{0},q_{1},...,q_{n}}، أينqأنا∈سؤال{\displaystyle q_{i}\in Q}بحيثqأنا=دلتا(qأنا-1،أأنا){\displaystyle q_{i}=\delta (q_{i-1},a_{i})}ل0<أنا≤ن{\displaystyle 0<i\leq n}، هو تشغيل الآلة على مدخلأ1أ2...أن∈Σ*{\displaystyle a_{1}a_{2}...a_{n}\in \Sigma ^{*}}بدءاً من الولايةq0{\displaystyle q_{0}}بمعنى آخر، يكون الجهاز في البداية في حالة البدايةq0{\displaystyle q_{0}}ويتلقى المدخلاتأ1{\displaystyle a_{1}}. لأ1{\displaystyle a_{1}}وكل ما يلي ذلكأأنا{\displaystyle a_{i}}في سلسلة الإدخال، يختار الجهاز الحالة التاليةqأنا{\displaystyle q_{i}}وفقًا لدالة الانتقالدلتا(qأنا-1،أأنا){\displaystyle \delta (q_{i-1},a_{i})}، حتى الرمز الأخيرأن{\displaystyle a_{n}}تمت قراءة البيانات، مما ترك الجهاز في الحالة النهائية للتشغيل.qن{\displaystyle q_{n}}وبالمثل، في كل خطوة، يُصدر الجهاز الآلي رمز إخراج وفقًا لدالة الإخراج.λ(qأنا-1،أأنا){\displaystyle \lambda (q_{i-1},a_{i})}.
دالة الانتقالدلتا{\displaystyle \delta }يتم توسيعها استقرائياً إلىدلتا¯:سؤال×Σ*→سؤال{\displaystyle {\overline {\delta }}:Q\times \Sigma ^{*}\to Q}لوصف سلوك الآلة عند إدخال كلمات كاملة. بالنسبة للسلسلة الفارغةε{\displaystyle \varepsilon }،دلتا¯(q،ε)=q{\displaystyle {\overline {\delta }}(q,\varepsilon )=q}لجميع الولاياتq{\displaystyle q}وبالنسبة للأوتارwأ{\displaystyle wa}أينأ{\displaystyle a}هو الرمز الأخير وw{\displaystyle w}وهو الجزء المتبقي من السلسلة (الذي قد يكون فارغًا)،دلتا¯(q،wأ)=دلتا(دلتا¯(q،w)،أ){\displaystyle {\overline {\delta }}(q,wa)=\delta ({\overline {\delta }}(q,w),a)}[ 10 ] دالة الإخراجλ{\displaystyle \lambda }ويمكن توسيع نطاقها بشكل مماثل إلىλ¯(q،w){\displaystyle {\overline {\lambda }}(q,w)}، مما يعطي الناتج الكامل للجهاز عند تشغيله على كلمةw{\displaystyle w}من الولايةq{\displaystyle q}.
مستقبل
من أجل دراسة الآلة باستخدام نظرية اللغات الرسمية ، يمكن اعتبار الآلة بمثابة مستقبل ، يحل محل أبجدية الإخراج ووظيفتها.Γ{\displaystyle \Gamma }وλ{\displaystyle \lambda }مع
  • q0∈سؤال{\displaystyle q_{0}\in Q}، وحالة بدء محددة ، و
  • F{\displaystyle F}، مجموعة من حالاتسؤال{\displaystyle Q}(أيF⊆سؤال{\displaystyle F\subseteq Q}) تسمى حالات القبول .
وهذا يسمح بتحديد ما يلي:
قبول الكلمة
كلمةw=أ1أ2...أن∈Σ*{\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}كلمة تقبل الآلة إذادلتا¯(q0،w)∈F{\displaystyle {\overline {\delta }}(q_{0},w)\in F}أي، إذا بعد استهلاك السلسلة بأكملهاw{\displaystyle w}الجهاز في حالة قبول.
لغة معترف بها
اللغةل⊆Σ*{\displaystyle L\subseteq \Sigma ^{*}}مجموعة الكلمات التي يقبلها الجهاز الآلي هي مجموعة جميع الكلمات التي يقبلها الجهاز الآلي.ل={w∈Σ* | دلتا¯(q0،w)∈F}{\displaystyle L=\{w\in \Sigma ^{*}\ |\ {\overline {\delta }}(q_{0},w)\in F\}}[ 13 ]​
لغات مفهومة
اللغات القابلة للتمييز هي مجموعة اللغات التي تتعرف عليها بعض الآلات. بالنسبة للآلات المحدودة، تكون اللغات القابلة للتمييز هي اللغات المنتظمة . وتختلف هذه اللغات باختلاف أنواع الآلات.

تعريفات متنوعة للآلات

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

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

تؤدي التوليفات المختلفة للاختلافات المذكورة أعلاه إلى إنتاج العديد من فئات الآلات.

نظرية الأوتوماتا هي مجالٌ يدرس خصائص أنواع مختلفة من الأوتوماتا. على سبيل المثال، تُدرس الأسئلة التالية حول نوع معين من الأوتوماتا.

  • أي فئة من اللغات الرسمية يمكن التعرف عليها بواسطة نوع من أنواع الآلات؟ (اللغات القابلة للتعرف عليها)
  • هل بعض الآلات مغلقة تحت اتحاد أو تقاطع أو تكملة اللغات الرسمية؟ (خصائص الإغلاق)
  • ما مدى قدرة نوع معين من الآلات على التعبير عن فئة من اللغات الرسمية؟ وما هي قدرتها التعبيرية النسبية؟ (التسلسل الهرمي للغات)

تدرس نظرية الأوتوماتا أيضاً وجود أو عدم وجود أي خوارزميات فعالة لحل المشكلات المشابهة للقائمة التالية:

  • هل يقبل جهاز الآلة كلمة إدخال واحدة على الأقل؟ (التحقق من الفراغ)
  • هل من الممكن تحويل آلة غير حتمية معينة إلى آلة حتمية دون تغيير اللغة التي تتعرف عليها؟ (الحتمية)
  • بالنسبة للغة رسمية معينة، ما هو أصغر جهاز آلي يتعرف عليها؟ ( التقليل )

أنواع الأوتوماتا

فيما يلي قائمة غير مكتملة لأنواع الآلات.

آلةلغات مفهومة
آلة الحالة المحدودة غير الحتمية/الحتمية (FSM)اللغات العادية
آلة الدفع الحتمية (DPDA)اللغات الحتمية الخالية من السياق
جهاز الدفع الآلي (PDA)اللغات الخالية من السياق
الأوتومات الخطي المحدود (LBA)اللغات الحساسة للسياق
آلة تورينجاللغات القابلة للتعداد بشكل متكرر
آلة بوشي الحتميةلغات ذات حد ω
آلة بوشي غير الحتميةاللغات المنتظمة من النوع ω
آلة رابين الآلية ، آلة ستريت الآلية ، آلة التكافؤ الآلية ، آلة مولر الآلية
الأوتوماتون الموزون

الأوتوماتا المنفصلة والمتصلة والهجينة

عادةً ما تصف نظرية الأوتوماتا حالات الآلات المجردة، ولكن هناك أوتوماتا منفصلة، ​​أو أوتوماتا تناظرية ، أو أوتوماتا مستمرة ، أو أوتوماتا هجينة منفصلة-مستمرة ، والتي تستخدم البيانات الرقمية، أو البيانات التناظرية، أو الوقت المستمر، أو البيانات الرقمية والتناظرية ، على التوالي.

التسلسل الهرمي من حيث السلطات

فيما يلي تسلسل هرمي غير مكتمل من حيث قدرات أنواع مختلفة من الآلات الافتراضية. يعكس هذا التسلسل الهرمي الفئات المتداخلة للغات التي تستطيع هذه الآلات قبولها. [ 14 ]

آلة
الأوتوماتون الحتمي المحدود (DFA) - أقل استهلاك للطاقة

(نفس القوة)  ||{\displaystyle ||}  (نفس القوة) الأوتوماتون المحدود غير الحتمي (NFA) (ما سبق أضعف)  ∩{\displaystyle \cap }  (الخيار أدناه أقوى) آلة الدفع الحتمية (DPDA-I) مع مخزن دفع واحد ∩{\displaystyle \cap }آلة دفع غير حتمية (NPDA-I) مع مخزن دفع واحد ∩{\displaystyle \cap }الأوتومات الخطي المحدود (LBA) ∩{\displaystyle \cap }آلة الدفع الحتمية (DPDA-II) مزودة بمخزنين للدفع ||{\displaystyle ||}آلة دفع غير حتمية (NPDA-II) مزودة بمخزنين للدفع لأسفل ||{\displaystyle ||}آلة تورينج الحتمية (DTM) ||{\displaystyle ||}آلة تورينج غير الحتمية (NTM) ||{\displaystyle ||}آلة تورينج الاحتمالية (PTM) ||{\displaystyle ||}آلة تورينج متعددة الأشرطة (MTM) ||{\displaystyle ||}آلة تورينج متعددة الأبعاد

التطبيقات

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

محاكيات الأتمتة

تُعدّ برامج محاكاة الأوتوماتا أدوات تعليمية تُستخدم لتدريس وتعلم وبحث نظرية الأوتوماتا. يستقبل برنامج محاكاة الأوتوماتا وصفًا للأوتوماتا كمدخل، ثم يُحاكي طريقة عملها لسلسلة نصية مُدخلة عشوائية. يمكن إدخال وصف الأوتوماتا بعدة طرق، منها تعريفها بلغة رمزية، أو إدخال مواصفاتها في نموذج مُصمّم مسبقًا، أو رسم مخطط انتقالاتها بالنقر والسحب باستخدام الفأرة. من أشهر برامج محاكاة الأوتوماتا: عالم تورينج، وJFLAP، وVAS، وTAGS، وSimStudio. [ 16 ]

النماذج النظرية للفئات

يمكن تعريف عدة فئات متميزة من الأوتوماتا [ 17 ] باتباع تصنيف الأوتوماتا إلى أنواع مختلفة كما هو موضح في القسم السابق. تُعدّ الفئة الرياضية للأوتوماتا الحتمية، والآلات التسلسلية ، والأوتوماتا التسلسلية ، وآلات تورينج ذات تشاكلات الأوتوماتا التي تُعرّف الأسهم بين الأوتوماتا ، فئة ديكارتية مغلقة [ 18 ] ، ولها حدود فئوية ونهايات مشتركة . يُسقط تشاكل الأوتوماتا خماسية من أوتوماتا A <sub> i</sub> على خماسية من أوتوماتا أخرى A <sub> j</sub> . يمكن أيضًا اعتبار تشاكلات الأوتوماتا تحويلات للأوتوماتا أو تشاكلات شبه زمرة ، عندما تُعرّف فضاء الحالة S للأوتوماتا على أنه شبه زمرة S <sub> g</sub> . تُعتبر المونويدات أيضًا إطارًا مناسبًا للأوتوماتا في الفئات المونويدية [ 19 ] [ 20 ] [ 21 ] .

فئات الأوتوماتا المتغيرة

يمكن أيضاً تعريف آلة متغيرة ، بالمعنى الذي ذكره نوربرت وينر في كتابه " الاستخدام البشري للبشر" من خلال التشاكلات الداخلية.أأنا→أأنا{\displaystyle A_{i}\to A_{i}}عندئذٍ، يمكن إثبات أن تشاكلات الأوتوماتا المتغيرة هذه تُشكّل زمرة رياضية. في حالة الأوتوماتا غير الحتمية، أو الأنواع المعقدة الأخرى منها، قد تُصبح مجموعة التشاكلات الداخلية الأخيرة زمرة جزئية للأوتوماتا المتغيرة . لذلك، في الحالة العامة، تُعدّ فئات الأوتوماتا المتغيرة من أي نوع فئات زمر جزئية أو فئات زمر جزئية . علاوة على ذلك، تُصبح فئة الأوتوماتا العكسية فئة ثنائية ، وهي أيضًا فئة فرعية من الفئة الثنائية للزمر الجزئية، أو فئة الزمر الجزئية.

انظر أيضاً

مراجع

  1. ↑ ماهوني، مايكل س. "هياكل الحوسبة والبنية الرياضية للطبيعة" . مجلة روثرفورد . تم الاسترجاع في 7 يونيو 2020 .
  2. ↑ بوث، تايلور (1967). الآلات التسلسلية ونظرية الأوتوماتا . نيويورك: جون وايلي وأولاده. ص 1-13. ISBN  0-471-08848-X.
  3. ↑ آشبي، ويليام روس (15 يناير 1967). "مكانة الدماغ في العالم الطبيعي" (ملف PDF) . تيارات في علم الأحياء الحديث . 1 (2): 95-104 . رمز Bibcode : 1967BiSys...1...95A . doi : 10.1016/0303-2647(67)90021-4 . PMID 6060865. مؤرشف من الأصل (ملف PDF) بتاريخ 4 يونيو 2023. تم الاطلاع عليه بتاريخ 29 مارس 2021 . : "إن النظريات، التي تطورت بشكل جيد الآن، لـ "آلة الحالة المحدودة" (جيل، 1962)، و"المحول عديم الضوضاء" (شانون وويفر، 1949)، و"النظام المحدد بالحالة" (آشبي، 1952)، و"الدائرة التسلسلية"، متماثلة بشكل أساسي."
  4. ↑ آشبي، دبليو آر؛ وآخرون (1956). سي إي شانون؛ جيه مكارثي (محرران). دراسات في الأوتوماتا . برينستون، نيوجيرسي: مطبعة جامعة برينستون. 
  5. 1 2 3 4 5 أربيب، مايكل (1969). نظريات الأوتوماتا المجردة . إنجلوود كليفس، نيوجيرسي: برنتيس هول.
  6. ↑ لي، مينغ؛ بول، فيتاني (1997). مقدمة في تعقيد كولموغوروف وتطبيقاته . نيويورك: سبرينغر-فيرلاغ. ص 84. 
  7. ↑ تشومسكي، نعوم (1956). "ثلاثة نماذج لوصف اللغة" (ملف PDF) . معاملات IRE في نظرية المعلومات . 2 (3): 113-124 . doi : 10.1109/TIT.1956.1056813 . S2CID 19519474. مؤرشف (ملف PDF) من الأصل بتاريخ 2016-03-07 . 
  8. ↑ نيرود، أ. (1958). "تحويلات الأوتوماتون الخطي" . وقائع الجمعية الرياضية الأمريكية . 9 (4): 541. doi : 10.1090/S0002-9939-1958-0135681-9 .
  9. ↑ رابين، مايكل ؛ سكوت، دانا (أبريل 1959). "الآلات المحدودة ومشاكل اتخاذ القرار الخاصة بها" (ملف PDF) . مجلة IBM للبحوث والتطوير . 3 (2): 114-125 . doi : 10.1147/rd.32.0114 . مؤرشف من الأصل بتاريخ 14 ديسمبر 2010.
  10. 1 2 3 هارتمانيس، ج .؛ ستيرنز، ر. إي. (1966). نظرية البنية الجبرية للآلات التسلسلية . إنجلوود كليفس، نيوجيرسي: برنتيس هول.
  11. ↑ هارتمانيس، ج.؛ ستيرنز، ر. إي. (1964). "التعقيد الحسابي للتسلسلات المتكررة" (PDF) .
  12. ↑ فورتناو، لانس؛ هومر، ستيف (2002). "تاريخ موجز للتعقيد الحسابي" (PDF) .
  13. ↑ مور، كريستوفر (2019-07-31). "الآلات واللغات والقواعد النحوية". arXiv : 1907.12713 [ cs.CC ].
  14. ↑ يان، سونغ ي. (1998). مقدمة في اللغات الرسمية والحوسبة الآلية . سنغافورة: دار النشر العالمية العلمية المحدودة. ص 155-156 . ISBN  978-981-02-3422-5.
  15. ↑ فيراغوتي، أ.؛ ميشيلي، ج.؛ شنايدر، ر. (2018)، تركيبات غير قابلة للاختزال لكثيرات الحدود من الدرجة الثانية على الحقول المنتهية لها بنية منتظمة ، المجلة الفصلية للرياضيات، المجلد 69، مطبعة جامعة أكسفورد، الصفحات 1089-1099 ، arXiv : 1701.06040 ، doi : 10.1093/qmath/hay015 ، S2CID 3962424   
  16. ↑ تشاكرابورتي، ب.؛ ساكسينا، ب.س.؛ كاتي، س.ب. (2011). "خمسون عامًا من محاكاة الأوتوماتا: مراجعة" . ACM Inroads . 2 (4): 59-70 . doi : 10.1145/2038876.2038893 . S2CID 6446749 . 
  17. ^ جيري أداميك وفيرا ترنكوفا . 1990. الأتمتة والجبر في الفئات . كلوير للنشر الأكاديمي: دوردريخت وبراغ
  18. ↑ ماك لين، سوندرز (1971). تصنيفات للرياضي العامل . نيويورك: سبرينغر. ISBN 978-0-387-90036-0.
  19. ↑ https://www.math.cornell.edu/~worthing/asl2010.pdf جيمس وورثينجتون. 2010. التحديد والنسيان والأتمتة في الفئات المونيدية. الاجتماع السنوي لأمريكا الشمالية للغة الإشارة الأمريكية، 17 مارس 2010
  20. ↑ أغيار، م. وماهاجان، س.2010. "الوظائف الأحادية، والأنواع، وجبر هوبف" .
  21. ↑ ميسيجوير، ج.، مونتاناري، يو.: 1990 شبكات بتري هي أحاديات. المعلومات والحوسبة 88 : 105-155

للمزيد من القراءة