ما هو الانتظام؟

Question

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

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

Answer 1

أصل اسم الاسم يأتي من عمل كلاين 1950s الذي يصف مجموعات منتظمة باستخدام تدوينه الرياضي الذي تم إنشاؤه لهذا الغرض. يرى هذه.

Answer 2

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

لغة منتظمة هي واحدة يمكن تحديدها بواسطة آلة تعادل حسابية للأتمتة المحدودة (DFA / NDFA). يمكن اعتبار Automata المحدود كآلة تعمل بحتة في الولايات، ولا تخزين. حتى تتمكن من رؤية ذلك^نب^ن لا يمكن أن تكون منتظمة لأنها تتطلب آلة يمكنها حساب عدد A's و B (وبالتالي يجب أن يكون لها سعة تخزين غير محدودة) من أجل مقارنتها.

للمقارنة (ABC)^ن يكون منتظم، لأن عدد التكرار غير ذي صلة.

للحصول على عرض أكثر صرامة (وأكثال المقابلة) تحقق من ويكيبيديا المادة والصفحات المرتبطة.

_{* لا نهائي لا يهم هنا، لكنني أذكره من أجل الاكتمال. قد يكون من الأسهل التفكير في الأمر بأنه "لحسن الحظ، دائما ما يكفي".}

Answer 3

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

من الناحية النظرية، اللغة العادية (مجموعة من السلاسل) هي تلك التي يمكن إنشاؤها باستخدام إنسان آلي ذو حالة محدودة.من حيث المبرمج، هذا يعادل القول أنه يمكن إنشاؤه باستخدام التعبيرات العادية.وبالتالي، فإن جميع اللغات المحدودة (مجموعات السلاسل) منتظمة، ولكن هناك بعض اللغات اللانهائية، مثل a^نب^ن (لغة ​​جميع سلاسل n a's متبوعة بـ n b's) التي لا يمكن التعرف عليها باستخدام FSA أو التعبيرات العادية.هناك أجهزة حسابية أكثر قوة (مثل أجهزة الكمبيوتر الحديثة، والتي تم تصميمها باستخدام آلات تورينج) أيّ يستطيع التعرف على تلك اللغات.

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

Answer 4

الكلمة regular في regular expression يشير إلى المفهوم الرياضي العادي، وليس مفهوم اللغة الإنجليزية. تماما مثل كيف الكلمة prime في الرياضيات تحمل علاقة قليلة ب براي لحم بقري.

لقد ورثته CS (وهو فرع من الرياضيات) للإشارة إلى مفهوم أكثر تحديدا: http://en.wikipedia.org/wiki/regular_language.

Answer 5

التعبير المنتظم ليس منتظما بالفعل، الاسم ذو مهام.