القدرة التعبيرية (علوم الحاسوب)

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

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

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

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

هناك بعض النتائج المتعلقة بالإيجاز أيضًا؛ على سبيل المثال، تعتبر الأوتوماتا المحدودة غير الحتمية والقواعد النحوية المنتظمة أكثر إيجازًا من التعبيرات النمطية، بمعنى أنه يمكن ترجمة الأخيرة إلى الأولى دون زيادة كبيرة في الحجم (أي في O(1) )، بينما العكس غير ممكن.

تنطبق اعتبارات مماثلة على الأشكال التي لا تصف مجموعات من السلاسل النصية، بل مجموعات من الأشجار (مثل لغات مخطط XML )، أو الرسوم البيانية ، أو الهياكل الأخرى.

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

اتضح أن منطق الرتبة الأولى يفتقر إلى القدرة التعبيرية: فهو لا يستطيع التعبير عن أنواع معينة من الاستعلامات المنطقية، مثل الاستعلامات التي تتضمن إغلاقًا متعديًا . ^{[ 6 ]} ومع ذلك، يجب إضافة القدرة التعبيرية بحذر: إذ يجب أن يظل من الممكن تقييم الاستعلامات بكفاءة معقولة، وهو ما لا يتحقق، على سبيل المثال، في منطق الرتبة الثانية . ونتيجة لذلك، ظهرت دراسات تقارن بين العديد من لغات الاستعلام وبنياتها اللغوية على أساس القدرة التعبيرية والكفاءة، مثل إصدارات مختلفة من لغة داتالوج . ^{[ 7 ]}

تنطبق اعتبارات مماثلة على لغات الاستعلام على أنواع أخرى من البيانات، على سبيل المثال لغات استعلام XML مثل XQuery .