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