اللغة العادية

في علم الحاسوب النظري ونظرية اللغة الرسمية ، فإن اللغة المنتظمة (وتسمى أيضًا اللغة العقلانية ) ^{[ 1 ] [ 2 ]} هي لغة رسمية يمكن تعريفها بواسطة تعبير منتظم ، بالمعنى الدقيق في علم الحاسوب النظري (على عكس العديد من محركات التعبير المنتظم الحديثة، والتي تم تعزيزها بميزات تسمح بالتعرف على اللغات غير المنتظمة).

بدلاً من ذلك، يمكن تعريف اللغة المنتظمة بأنها لغة تتعرف عليها آلة حالة منتهية . يُعرف تكافؤ التعابير المنتظمة وآلات الحالة المنتهية بنظرية كلين ^{[ 3 ]} (نسبةً إلى عالم الرياضيات الأمريكي ستيفن كول كلين ). في التسلسل الهرمي لتشومسكي ، تُعتبر اللغات المنتظمة هي اللغات التي تولدها قواعد النحو من النوع الثالث .

يتم تعريف مجموعة اللغات المنتظمة على الأبجدية Σ بشكل متكرر على النحو التالي:

• اللغة الفارغة ∅ هي لغة منتظمة.
• لكل a ∈ Σ ( a ينتمي إلى Σ)، فإن لغة الأحادية { a } هي لغة منتظمة.
• إذا كانت A لغة منتظمة، فإن A * ( نجمة كلين ) هي لغة منتظمة. وبناءً على ذلك، فإن لغة السلسلة الفارغة {ε} هي لغة منتظمة أيضًا.
• إذا كانت A و B لغات منتظمة، فإن A ∪ B (الاتحاد) و A • B (التسلسل) لغات منتظمة.
• لا توجد لغات أخرى فوق Σ منتظمة.

انظر قسم التعبيرات النمطية §  نظرية اللغة الرسمية للاطلاع على بناء الجملة ودلالات التعبيرات النمطية.

جميع اللغات المنتهية منتظمة؛ وعلى وجه الخصوص، لغة السلاسل الفارغة {ε} = ∅* منتظمة. ومن الأمثلة النموذجية الأخرى اللغة التي تتكون من جميع السلاسل المكونة من الأبجدية { a , b } والتي تحتوي على عدد زوجي من الحرف a ، أو اللغة التي تتكون من جميع السلاسل التي تأخذ الشكل التالي: عدة أحرف a متبوعة بعدة أحرف b .

من الأمثلة البسيطة على اللغات غير المنتظمة مجموعة السلاسل { a ⁿ b ⁿ | n ≥ 0 } . ^{[ 4 ]} وبشكل بديهي، لا يمكن التعرف عليها باستخدام آلة حالة منتهية، لأن ذاكرة الآلة منتهية محدودة ولا يمكنها تذكر العدد الدقيق للحرف a. فيما يلي تقنيات لإثبات هذه الحقيقة بدقة .

اللغة المنتظمة تحقق الخصائص المتكافئة التالية:

1. إنها لغة التعبير النمطي (وفقًا للتعريف أعلاه)
2. إنها اللغة التي تقبلها آلة الحالة المحدودة غير الحتمية (NFA) ^{[ ملاحظة 1 ] [ ملاحظة 2 ]}
3. إنها اللغة التي تقبلها آلة الحالة المحدودة الحتمية (DFA) ^{[ ملاحظة 3 ] [ ملاحظة 4 ]}
4. يمكن توليدها بواسطة قواعد نحوية منتظمة ^{[ ملاحظة 5 ] [ ملاحظة 6 ]}
5. إنها اللغة التي يقبلها جهاز آلي محدود متناوب
6. إنها اللغة التي يقبلها جهاز آلي محدود ثنائي الاتجاه
7. يمكن توليدها بواسطة قواعد البادئة
8. يمكن قبولها بواسطة آلة تورينج للقراءة فقط
9. يمكن تعريفها في منطق الرتبة الثانية الأحادي ( نظرية بوشي-إلجوت-تراختينبروت ) ^{[ 5 ]}
10. يتم التعرف عليه بواسطة بعض أحاديات التركيب المحدودة M ، مما يعني أنه الصورة العكسية { w ∈ Σ ^* | f ( w ) ∈ S } لمجموعة جزئية S من أحادي محدود M تحت تشاكل أحادي f  : Σ ^* → M من الأحادي الحر على أبجديته ^{[ ملاحظة 7 ]}
11. عدد فئات التكافؤ لتطابقها النحوي محدود. ^{[ ملاحظة 8 ] [ ملاحظة 9 ]} (هذا العدد يساوي عدد حالات الآلة المحدودة الحتمية الدنيا التي تقبل L. )

الخاصيتان 10 و11 هما مقاربتان جبريتان بحتتان لتعريف اللغات المنتظمة؛ ويمكن صياغة مجموعة مماثلة من العبارات لـ M ⊆ Σ ^* . في هذه الحالة، يؤدي التكافؤ على M إلى مفهوم اللغة القابلة للتمييز.

يستخدم بعض المؤلفين إحدى الخصائص المذكورة أعلاه، والتي تختلف عن "1."، كتعريف بديل للغات المنتظمة.

تُعرف بعض المكافئات المذكورة أعلاه، ولا سيما تلك المتعلقة بالصيغ الأربع الأولى، باسم " نظرية كلين" في الكتب الدراسية. ويختلف المؤلفون في تحديد أيّها (أو أيّ مجموعة فرعية) يُطلق عليه هذا الاسم. يُطلق أحد الكتب الدراسية على تكافؤ التعابير النمطية والآلات غير القطعية المحدودة (NFAs) ("1." و"2." أعلاه) اسم "نظرية كلين". ^{[ 6 ]} ويُطلق كتاب دراسي آخر على تكافؤ التعابير النمطية والآلات القطعية المحدودة (DFAs) ("1." و"3." أعلاه) اسم "نظرية كلين". ^{[ 7 ]} بينما يُثبت كتابان دراسيان آخران أولًا التكافؤ التعبيري بين الآلات غير القطعية المحدودة والآلات القطعية المحدودة ("2." و"3.")، ثم يذكران "نظرية كلين" على أنها التكافؤ بين التعابير النمطية والآلات القطعية المحدودة (التي يُقال إنها تصف "اللغات القابلة للتمييز"). ^{[ 2 ] [ 8 ]} يبدأ نصٌ ذو توجه لغوي بمساواة القواعد النحوية المنتظمة ("4." أعلاه) مع آلات الحالة المحدودة المحددة (DFAs) وآلات الحالة المحدودة غير المحددة (NFAs)، ويُطلق على اللغات المُولَّدة بواسطة (أيٍّ من) هذه الآلات اسم "اللغات المنتظمة"، ثم يُقدِّم التعبيرات النمطية التي يُطلق عليها اسم "اللغات العقلانية"، وأخيرًا يُصرِّح بـ"نظرية كلين" باعتبارها تطابق اللغات المنتظمة والعقلانية. ^{[ 9 ]} يُعرِّف مؤلفون آخرون ببساطة "التعبير العقلاني" و"التعبيرات النمطية" على أنهما مترادفان، ويفعلون الشيء نفسه مع "اللغات العقلانية" و"اللغات المنتظمة". ^{[ 1 ] [ 2 ]}

يبدو أن مصطلح "منتظم" يعود أصله إلى تقرير فني نُشر عام ١٩٥١، حيث قدّم كلين مفهوم "الأحداث المنتظمة " ورحّب صراحةً "بأي اقتراحات لمصطلح أكثر وصفًا". ^{[ ١٠ ]} استخدم نعوم تشومسكي ، في مقالته الرائدة عام ١٩٥٩، مصطلح " منتظم" بمعنى مختلف في البداية (مشيرًا إلى ما يُعرف اليوم بصيغة تشومسكي الطبيعية )، ^{[ ١١ ]} لكنه لاحظ أن لغاته ذات الحالات المحدودة تُعادل أحداث كلين المنتظمة . ^{[ ١٢ ]}

اللغات المنتظمة مغلقة تحت عمليات مختلفة، أي إذا كانت اللغتان K و L منتظمتين، فإن نتيجة العمليات التالية تكون كذلك:

• العمليات المنطقية في نظرية المجموعات : الاتحاد K ∪ L ، والتقاطع K ∩ L ، والمكمل L ، وبالتالي المكمل النسبي K − L أيضًا . ^{[ 13 ]}
• العمليات الاعتيادية: K ∪ L ، عملية الربط${\displaystyle K\circ L}$ونجمة كلين L ^* . [ ^{14 ]​}
• العمليات الثلاث : تماثل السلاسل ، وتماثل السلاسل العكسي، والتقاطع مع اللغات المنتظمة. ونتيجةً لذلك، فهي مغلقة تحت أي تحويلات حالة محدودة ، مثل قسمة K / L على لغة منتظمة. بل إن اللغات المنتظمة مغلقة تحت عمليات القسمة على أي لغة : إذا كانت L منتظمة، فإن ^L / K تكون منتظمة لأي K. ^{[ 15} ]
• الصورة المعكوسة (أو صورة المرآة) LR. [ ^{16 ] بافتراض وجود} آلة حالة محدودة غير حتمية للتعرف على L ، يمكن الحصول على آلة حالة لـ ^LR عن طريق عكس جميع الانتقالات وتبديل حالات البداية والنهاية. قد ينتج عن ذلك حالات بداية متعددة؛ ويمكن استخدام انتقالات إبسيلون لربطها.

بفرض وجود آلتين حتميتين محدودتين A و B ، يمكن تحديد ما إذا كانتا تقبلان اللغة نفسها. ^{[ 17 ]} ونتيجة لذلك، وباستخدام خصائص الإغلاق المذكورة أعلاه ، يمكن أيضًا تحديد المسائل التالية لآلتين حتميتين محدودتين A و B معطاة بشكل عشوائي ، مع اللغتين المقبولتين L _A و L _B على التوالي:

• الاحتواء: هل L _A ⊆ L _B  ؟ ^{[ ملاحظة 10 ]}
• عدم التداخل: هل L _A ∩ L _B = {}  ؟
• الفراغ: هل L _A = {}  ؟
• الشمولية: هل L _A = Σ ^*  ؟
• العضوية: إذا كان a ∈ Σ ^* ، فهل a ∈ L _B  ؟

بالنسبة للتعبيرات النمطية، تُعدّ مسألة الشمولية مسألة NP-كاملة حتى مع أبجدية أحادية. ^{[ 18 ]} أما بالنسبة للأبجديات الأكبر، فتُعدّ هذه المسألة مسألة PSPACE-كاملة . ^{[ 19 ]} إذا تم توسيع التعبيرات النمطية لتشمل عامل التربيع ، حيث يُشير " A ² " إلى نفس معنى " AA "، فسيظل بالإمكان وصف اللغات النمطية فقط، ولكن مسألة الشمولية لها حد أدنى في الفضاء الأسي، ^{[ 20 ] [ 21 ] [ 22 ]} وهي في الواقع كاملة في الفضاء الأسي فيما يتعلق بالاختزال في زمن متعدد الحدود. ^{[ 23 ]}

بالنسبة لأبجدية محدودة ثابتة، فإن نظرية مجموعة جميع اللغات - بالإضافة إلى السلاسل النصية، وانتماء سلسلة نصية إلى لغة ما، ودالة لكل حرف لإلحاقه بسلسلة نصية (دون أي عمليات أخرى) - قابلة للتقرير، ويتكون هيكلها الفرعي الأولي الأدنى تحديدًا من اللغات المنتظمة. أما بالنسبة للأبجدية الثنائية، فتُسمى هذه النظرية S2S . ^{[ 24 ]}

في نظرية التعقيد الحسابي ، يُشار أحيانًا إلى فئة تعقيد جميع اللغات المنتظمة بالاختصار REGULAR أو REG ، وتساوي DSPACE (O(1))، أي مسائل القرار التي يمكن حلها في مساحة ثابتة (المساحة المستخدمة مستقلة عن حجم المدخلات). REGULAR ≠ AC ⁰ ، لأنها (بشكل بديهي) تحتوي على مسألة التكافؤ لتحديد ما إذا كان عدد البتات التي قيمتها 1 في المدخلات زوجيًا أم فرديًا، وهذه المسألة غير موجودة في AC ^{0. [ 25 ]} من ناحية أخرى، لا تحتوي REGULAR على AC ⁰ ، لأن اللغة غير المنتظمة هي لغة المتناظرات ، أو اللغة غير المنتظمة${\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}$يمكن التعرف على كليهما ^في AC ^0. [ ^{26 ]}

إذا لم تكن اللغة منتظمة، فإنها تتطلب جهازًا بسعة تخزين لا تقل عن Ω (log log n ) للتعرف عليها (حيث n هو حجم المدخلات). ^{[ 27 ]} بعبارة أخرى، DSPACE( Ω (log log n )) يساوي فئة اللغات المنتظمة. ^{[ 27 ]} عمليًا، تُدرس معظم المسائل غير المنتظمة في بيئة ذات سعة تخزين لا تقل عن Ω (log log n)، لأن هذه هي سعة التخزين المطلوبة لتخزين مؤشر في شريط الإدخال. ^{[ 28 ]}

لتحديد اللغات المنتظمة في تسلسل تشومسكي الهرمي ، يُلاحظ أن كل لغة منتظمة خالية من السياق . لكن العكس ليس صحيحًا: على سبيل المثال، اللغة التي تتكون من جميع السلاسل التي تحتوي على نفس عدد الأحرف a و b هي لغة خالية من السياق ولكنها ليست منتظمة. لإثبات أن لغة ما ليست منتظمة، يُستخدم غالبًا مبرهنة مايهيل-نيرود ومبرهنة الضخ . وتشمل الطرق الأخرى استخدام خصائص الإغلاق للغات المنتظمة ^{[ 29 ]} أو تحديد تعقيد كولموغوروف كميًا ^{[ 30 ]} .

تشمل الفئات الفرعية المهمة للغات المنتظمة ما يلي:

• اللغات المحدودة، هي تلك التي تحتوي على عدد محدود من الكلمات فقط. ^{[ 31 ]} هذه لغات منتظمة، حيث يمكن إنشاء تعبير منتظم يمثل اتحاد كل كلمة في اللغة.
• اللغات الخالية من النجوم ، وهي تلك التي يمكن وصفها بتعبير منتظم مُنشأ من الرمز الفارغ، والحروف، والتسلسل، وجميع عوامل التشغيل المنطقية (انظر جبر المجموعات ) بما في ذلك المكمل ولكن ليس نجمة كلين : تشمل هذه الفئة جميع اللغات المنتهية. ^{[ 32 ]}

يترك${\displaystyle s_{L}(n)}$يشير إلى عدد الكلمات ذات الطول${\displaystyle n}$في${\displaystyle L}$الدالة المولدة العادية لـ L هي متسلسلة القوى الرسمية

${\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}$

تكون الدالة المولدة للغة L دالة كسرية إذا كانت L لغة منتظمة. ^{[ 33 ]} وبالتالي، لكل لغة منتظمة${\displaystyle L}$التسلسل${\displaystyle s_{L}(n)_{n\geq 0}}$هي دالة ثابتة متكررة ؛ أي أنه يوجد ثابت صحيح${\displaystyle n_{0}}$، الثوابت المركبة${\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}}$وكثيرات الحدود المعقدة${\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)}$بحيث يكون لكل${\displaystyle n\geq n_{0}}$الرقم${\displaystyle s_{L}(n)}$من الكلمات الطويلة${\displaystyle n}$في${\displaystyle L}$يكون${\displaystyle s_{L}(n)=p_{1}(n)\lambda _ {1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}$[ ^{34 ] [ 35 ] [ 36 ] [ 37 ]​}

وبالتالي، فإن عدم انتظام بعض اللغات${\displaystyle L'}$يمكن إثبات ذلك عن طريق عدّ الكلمات ذات الطول المحدد في ${\displaystyle L'}$لنأخذ على سبيل المثال لغة ديك المكونة من سلاسل من الأقواس المتوازنة. عدد الكلمات ذات الطول${\displaystyle 2n}$ في لغة ديك يساوي العدد الكاتالوني${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}$، وهو ليس من الشكل${\displaystyle p(n)\lambda ^{n}}$، مما يدل على عدم انتظام لغة ديك. يجب توخي الحذر لأن بعض القيم الذاتية${\displaystyle \lambda _{i}}$قد يكون لها نفس الحجم. على سبيل المثال، عدد الكلمات ذات الطول${\displaystyle n}$في لغة جميع الكلمات الثنائية، لا يكون الشكل${\displaystyle p(n)\lambda ^{n}}$لكن عدد الكلمات ذات الطول الزوجي أو الفردي يكون على هذا الشكل؛ والقيم الذاتية المقابلة هي${\displaystyle 2,-2}$بشكل عام، يوجد ثابت لكل لغة منتظمة${\displaystyle d}$بحيث يكون ذلك لجميع${\displaystyle a}$عدد الكلمات ذات الطول${\displaystyle dm+a}$هو تقاربياً${\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}$[ ^{38 ]​}

دالة زيتا للغة L هي ^{[ 33 ]}

${\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).}$

دالة زيتا للغة المنتظمة ليست كسرية بشكل عام، ولكن دالة زيتا للغة الدورية العشوائية تكون كسرية. ^{[ 39 ] [ 40 ]}

تم تعميم مفهوم اللغة المنتظمة ليشمل الكلمات اللانهائية (انظر ω-automata ) والأشجار (انظر tree automaton ).

تُعمم المجموعة العقلانية مفهوم اللغة المنتظمة/العقلانية ليشمل أحاديات ليست بالضرورة حرة . وبالمثل، فإن مفهوم اللغة القابلة للتمييز (بواسطة آلة حالة منتهية) له نظير في كونه مجموعة قابلة للتمييز على أحادي ليس بالضرورة حرًا. ويشير هوارد ستراوبينغ في هذا الصدد إلى أن "مصطلح "اللغة المنتظمة" غير دقيق إلى حد ما. فالأبحاث المتأثرة بدراسة إيلنبرغ [ ^{41 ] غالبًا} ما تستخدم إما مصطلح "اللغة القابلة للتمييز"، الذي يشير إلى سلوك آلات الحالة، أو مصطلح "اللغة العقلانية"، الذي يشير إلى أوجه التشابه المهمة بين التعبيرات النمطية ومتسلسلات القوى العقلانية . (في الواقع، يُعرّف إيلنبرغ المجموعات الجزئية العقلانية والقابلة للتمييز من أحاديات عشوائية؛ ولا يتطابق المفهومان، بشكل عام). هذه المصطلحات، على الرغم من أنها أكثر دقة، لم تنتشر على نطاق واسع، ويُستخدم مصطلح "اللغة المنتظمة" بشكل شبه عالمي." ^{[ 42 ]}

تُعدّ المتسلسلات الكسرية تعميمًا آخر، وهذه المرة في سياق متسلسلة قوى رسمية على شبه حلقة . يُنتج هذا النهج تعابير كسرية موزونة وأوتوماتا موزونة . في هذا السياق الجبري، تُسمى اللغات المنتظمة (المقابلة للتعابير الكسرية الموزونة منطقيًا ) عادةً باللغات الكسرية . ^{[ 43 ] [ 44 ]} وفي هذا السياق أيضًا، تُقدّم نظرية كلين تعميمًا يُسمى نظرية كلين-شوتزنبرغر .

• كلين، إس سي : تمثيل الأحداث في الشبكات العصبية والآلات المحدودة. في: شانون، سي إي، مكارثي، جيه (محرران) دراسات الآلات، ص  3-41. مطبعة جامعة برينستون، برينستون (1956)؛ وهي نسخة معدلة قليلاً من تقريره الصادر عام 1951 عن مؤسسة راند والذي يحمل نفس العنوان، RM704 .
• ساكاروفيتش، ج. (1987). "إعادة النظر في نظرية كلين". الاتجاهات والتقنيات والمشكلات في علوم الحاسوب النظرية . سلسلة محاضرات في علوم الحاسوب. المجلد  1987. الصفحات 39-50 . doi : 10.1007/3540185356_29 . ISBN  978-3-540-18535-2.

• حديقة حيوانات التعقيد : فئة REG