فهم آلات الدولة

مقدمة لمفاهيم علوم الكمبيوتر

تمكننا علوم الكمبيوتر من البرمجة ، ولكن من الممكن القيام بالكثير من البرمجة دون فهم المفاهيم الأساسية لعلوم الكمبيوتر.

هذا ليس شيئًا سيئًا دائمًا. عندما نبرمج ، فإننا نعمل على مستوى أعلى من التجريد.

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

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

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

ومع ذلك ، إذا كنت تخطط لكتابة التعليمات البرمجية التي تتطلب حسابًا جادًا ، فستحتاج إلى فهم المزيد حول كيفية عمل الحساب تحت الغطاء.

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

آلات الحالة المحدودة

آلة الحالة المحدودة هي تجريد رياضي يستخدم لتصميم الخوارزميات.

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

تخيل جهازًا يقرأ قطعة طويلة من الورق. لكل بوصة من الورق يوجد حرف واحد مطبوع عليها - إما الحرف "أ" أو الحرف "ب".

عندما تقرأ آلة الحالة كل حرف ، فإنها تغير الحالة. هنا آلة حالة بسيطة للغاية:

الدوائر هي " حالات " يمكن أن تكون فيها الآلة. الأسهم هي الانتقالات . لذا، إذا كنت في حالة الصورة وقراءة "أ"، عليك الانتقال إلى دولة ف . إذا قرأت حرف "ب" ، فستبقى في الولاية s .

لذلك إذا بدأنا في s وقرأنا الشريط الورقي أعلاه من اليسار إلى اليمين ، فسنقرأ الحرف "a" وننتقل إلى الحالة q .

ثم نقرأ حرف "ب" ونعود إلى الحالة s .

سيبقينا حرف "b" آخر على s ، متبوعًا بـ "a" - والذي يعيدنا إلى حالة q . بسيط بما فيه الكفاية ، ولكن ما هو الهدف؟

حسنًا ، اتضح أنه يمكنك تشغيل شريط عبر آلة الحالة وإخبار شيء عن تسلسل الحروف ، من خلال فحص الحالة التي ينتهي بها الأمر.

في آلة الحالة البسيطة أعلاه ، إذا انتهينا بالحالة s ، يجب أن ينتهي الشريط بحرف "b". إذا انتهينا بالحالة q ، ينتهي الشريط بالحرف "a".

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

يمكن لآلة الحالة أن تنتقل إلى حالة تُظهر أنها قد قرأت علامة html ، وحلقة التكرار حتى تصل إلى علامة head ، وحلقة حتى تصل إلى علامة إغلاق head ، وما إلى ذلك.

إذا نجحت في الوصول إلى الحالة النهائية ، فستحصل على تلك العلامات الخاصة بالترتيب الصحيح.

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

آلات الدولة المحدودة الحتمية

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

ما فائدة مجموعة القرارات إذا كان من الممكن أن يؤدي نفس المدخل إلى الانتقال إلى أكثر من حالة واحدة؟ لا يمكنك إخبار الكمبيوتر ، if x == trueثم التنفيذ doSomethingBigأو التنفيذ doSomethingSmall، أليس كذلك؟

حسنًا ، يمكنك نوعًا ما باستخدام آلة الدولة.

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

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

آلات الحالة المحدودة غير القطعية

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

على سبيل المثال ، لنفترض أننا نريد بناء آلة حالة محدودة يمكنها التعرف على سلاسل الحروف التي:

  • ابدأ بالحرف "أ"
  • ثم يتبعها صفر أو أكثر من تكرارات الحرف "ب"
  • أو ، صفر أو أكثر من تكرارات الحرف "c"
  • يتم إنهاء بالحرف التالي من الأبجدية.

السلاسل الصالحة ستكون:

  • abbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (صفر تواجدات ب)
  • إعلان (صفر تكرارات ج)

لذلك سوف يتعرف على الحرف "أ" متبوعًا بصفر أو أكثر من نفس الحرف "ب" أو "ج" ، متبوعًا بالحرف التالي من الأبجدية.

هناك طريقة بسيطة جدًا لتمثيل ذلك وهي باستخدام آلة حالة تشبه تلك الموجودة أدناه ، حيث تعني الحالة النهائية لـ t أنه تم قبول السلسلة وتطابق النمط.

هل ترى هذه المشكلة؟ من نقطة الانطلاق الصورة ، ونحن لا نعرف أي طريق لاتخاذ. إذا قرأنا الحرف "a" ، فإننا لا نعرف ما إذا كنا سنذهب إلى الحالة q أو r.

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

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

الخيار الآخر هو تحويل الآلة غير القطعية إلى آلة حتمية.

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

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

الآلة أدناه هي نسخة حتمية من الآلة غير القطعية أعلاه. في الجهاز أدناه ، يتم الوصول إلى الحالة النهائية لـ t أو v بواسطة أي سلسلة تقبلها الآلة.

يحتوي النموذج غير القطعي على أربع حالات وستة انتقالات. يحتوي النموذج القطعي على ست حالات وعشر انتقالات وحالتين نهائيتين محتملتين.

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

التعبيرات العادية

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

على سبيل المثال ، يمكن مطابقة النمط الموضح أعلاه مع التعبير العادي: a(b*c|c*d)

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

إذن ما نوع الأنماط التي لا يمكن مطابقتها؟ لنفترض أنك تريد مطابقة سلاسل "أ" و "ب" فقط ، حيث يوجد عدد من "أ" متبوعًا بعدد متساوٍ من "ب". أو n 'a's متبوعة بـ n ' b's ، حيث n هي رقم ما.

الأمثلة ستكون:

  • أب
  • عاب
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbb

في البداية ، يبدو هذا وكأنه مهمة سهلة لآلة الدولة المحدودة. تكمن المشكلة في أنك ستنفد بسرعة من الحالات ، أو سيتعين عليك افتراض عدد لا حصر له من الحالات - وعند هذه النقطة لم تعد آلة الحالة المحدودة .

لنفترض أنك قمت بإنشاء آلة حالة محدودة يمكنها قبول ما يصل إلى 20 'a' متبوعة بـ 20 'b's. يعمل هذا بشكل جيد ، حتى تحصل على سلسلة من 21 'a' متبوعة بـ 21 'b - عند هذه النقطة ستحتاج إلى إعادة كتابة جهازك للتعامل مع سلسلة أطول.

لأي سلسلة يمكنك التعرف عليها ، هناك سلسلة أطول قليلاً لا يستطيع جهازك التعرف عليها بسبب نفاد الذاكرة.

يُعرف هذا باسم Pumping Lemma والذي يقول بشكل أساسي: "إذا كان النمط الخاص بك يحتوي على قسم يمكن تكراره (مثل المقطع أعلاه) ، فإن النمط ليس منتظمًا".

وبعبارة أخرى، لا تعبير عادي ولا آلة الدولة محدودة يمكن بناؤها من شأنها أن تعترف كل السلاسل التي لا تتناسب مع النمط.

إذا نظرت بعناية ، ستلاحظ أن هذا النوع من الأنماط حيث يحتوي كل "أ" على "ب" مطابق ، يبدو مشابهًا جدًا لـ HTML. ضمن أي زوج من العلامات ، قد يكون لديك أي عدد من أزواج العلامات المطابقة الأخرى.

لذلك ، بينما يمكنك استخدام تعبير عادي أو آلة حالة محدودة للتعرف على ما إذا كانت صفحة HTML تحتوي على ؛ والعناصر بالترتيب الصحيح ، لا يمكنك استخدام تعبير عادي لمعرفة ما إذا كانت صفحة HTML بأكملها صالحة أم لا - لأن HTML ليس نمطًا عاديًا. ml >, ead>

آلات تورينج

إذن كيف تتعرف على الأنماط غير العادية ؟

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

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

آلات تورينج كاملة حسابيًا - بمعنى أن أي شيء يمكن حسابه ، يمكن حسابه على آلة تورينج.

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

تمنحنا آلات تورينج جهازًا ميكانيكيًا تخيليًا يتيح لنا تصور وفهم كيفية عمل العملية الحسابية. إنه مفيد بشكل خاص في فهم حدود الحساب. إذا كان هناك اهتمام ، فسأقوم بمقال آخر عن Turing Machines في المستقبل.

لماذا هذا مهم؟

لذلك ما هي النقطة؟ كيف سيساعدك هذا في إنشاء نموذج PHP التالي؟

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

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

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

تتيح لك مؤسسة في علوم الكمبيوتر تناول مشكلة لا تعرف كيفية حلها والسبب: "لا أعرف كيفية حل X ، لكني أعرف كيفية حل Y. وأعرف كيفية تحويل حل من أجل Y إلى حل لـ X. لذلك ، أعرف الآن كيفية حل X. "

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

نُشر في الأصل على blog.markshead.com في 11 فبراير 2018.