اللغة الرسمية

في المنطق والرياضيات وعلوم الحاسوب واللغويات ، اللغة الرسمية هي مجموعة من السلاسل التي يتم أخذ رموزها من مجموعة تسمى " الأبجدية ".

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

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

يدرس مجال نظرية اللغة الرسمية في المقام الأول الجوانب النحوية البحتة لهذه اللغات، أي أنماطها البنيوية الداخلية. وقد انبثقت نظرية اللغة الرسمية من علم اللغة، كوسيلة لفهم الانتظامات النحوية للغات الطبيعية . ^{[ 2 ]}

في القرن السابع عشر، تخيل غوتفريد لايبنتز ووصف لغة "الخاصية العالمية" ، وهي لغة عالمية ورسمية تستخدم الصور التوضيحية . وفي وقت لاحق، بحث كارل فريدريش غاوس مشكلة رموز غاوس . ^{[ 3 ]}

في منتصف القرن التاسع عشر، أسس جورج بول مجال الجبر البولياني ، وهو طريقة رسمية لوصف العمليات المنطقية باستخدام قيم الصواب وعوامل المجموعات. وفي كتابه "بحث في قوانين الفكر" ، أثبت أن الاستدلال المنطقي يمكن التعبير عنه ومعالجته من خلال المعادلات الرمزية. ^{[ 4 ]}

حاول غوتلوب فريجه تطبيق أفكار لايبنتز من خلال نظام تدويني، تم عرضه لأول مرة في كتابه "Begriffsschrift " (1879) وتطويره بشكل كامل في كتابه " Grundgesetze der Arithmetik" المكون من مجلدين (1893/1903). ^{[ 5 ]} وقد وصف هذا النظام "لغة رسمية للغة البحتة". ^{[ 6 ]}

شهد النصف الأول من القرن العشرين تطورات عديدة ذات صلة باللغات الرسمية. فقد نشر أكسل ثو أربع أوراق بحثية تتعلق بالكلمات واللغة بين عامي 1906 و1914. وقدّمت آخر هذه الأوراق ما أطلق عليه إميل بوست لاحقًا اسم "أنظمة ثو"، وعرضت مثالًا مبكرًا لمسألة غير قابلة للحل . ^{[ 7 ]} واستخدم بوست هذه الورقة لاحقًا كأساس لبرهان عام 1947 "على أن مسألة الكلمات لأنصاف الزمر غير قابلة للحل بشكل متكرر"، ^{[ 8 ]} ثم ابتكر النظام المعياري لإنشاء اللغات الرسمية.

في عام ١٩٠٧، قدّم ليوناردو توريس كيفيدو لغةً رسميةً لوصف الرسومات الميكانيكية (الأجهزة الميكانيكية) في فيينا . ونشر بحثًا بعنوان "Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas" ("حول نظام من الرموز والمصطلحات يهدف إلى تسهيل وصف الآلات"). ^{[ ٩ ]} وقد صنّفه هاينز زيمانيك على أنه مكافئ للغة برمجة للتحكم الرقمي في أدوات الآلات. ^{[ ١٠ ]}

ابتكر نعوم تشومسكي تمثيلاً مجرداً للغات الرسمية والطبيعية، يُعرف باسم التسلسل الهرمي لتشومسكي . ^{[ 11 ]} في عام 1959، طور جون باكوس صيغة باكوس-ناور لوصف بناء جملة لغة برمجة عالية المستوى، وذلك بعد عمله في إنشاء لغة فورتران . ^{[ 12 ]} كان بيتر ناور سكرتيراً/محرراً لتقرير ALGOL60، حيث استخدم فيه صيغة باكوس-ناور لوصف الجزء الرسمي من ALGOL60.

في سياق اللغات الرسمية، يمكن أن تكون الأبجدية أي مجموعة ؛ وتُسمى عناصرها حروفًا . قد تحتوي الأبجدية على عدد لا نهائي من العناصر؛ ^{[ ملاحظة 1 ]} مع ذلك، تُحدد معظم التعريفات في نظرية اللغات الرسمية أبجديات ذات عدد محدود من العناصر، وتنطبق العديد من النتائج عليها فقط. غالبًا ما يكون من المنطقي استخدام الأبجدية بالمعنى المعتاد للكلمة، أو بشكل أعم، أي ترميز حروف محدود مثل ASCII أو Unicode .

يمكن أن تكون الكلمة على أي أبجدية أي سلسلة منتهية من الأحرف . يُرمز لمجموعة جميع الكلمات على أبجدية معينة Σ عادةً بالرمز Σ ^* (باستخدام نجمة كلين ). طول الكلمة هو عدد الأحرف التي تتكون منها. لكل أبجدية، توجد كلمة واحدة فقط طولها صفر، وهي الكلمة الفارغة ، والتي يُرمز لها غالبًا بالرمز e أو ε أو λ أو حتى Λ. يمكن دمج كلمتين لتكوين كلمة جديدة، طولها يساوي مجموع طولي الكلمتين الأصليتين. نتيجة دمج كلمة مع الكلمة الفارغة هي الكلمة الأصلية.

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

بالنظر إلى مجموعة غير فارغة${\displaystyle \Sigma }$لغة رسمية${\displaystyle L}$زيادة${\displaystyle \Sigma }$هي مجموعة فرعية من${\displaystyle \Sigma ^{*}}$، أين${\displaystyle \Sigma ^{*}}$هي مجموعة جميع الكلمات الممكنة ذات الطول المحدود على${\displaystyle \Sigma }$نسمي هذه المجموعة${\displaystyle \Sigma }$أبجدية${\displaystyle L}$من ناحية أخرى، بالنظر إلى لغة رسمية${\displaystyle L}$زيادة${\displaystyle \Sigma }$كلمة${\displaystyle w\in \Sigma ^{*}}$يكون سليم التكوين إذا${\displaystyle w\in L}$وبالمثل، فإن التعبير${\displaystyle E\subseteq \Sigma ^{*}}$يكون سليم التكوين إذا${\displaystyle E\subseteq L}$أحيانًا، لغة رسمية${\displaystyle L}$زيادة${\displaystyle \Sigma }$يحتوي على مجموعة من القواعد والقيود الواضحة لإنشاء جميع الكلمات السليمة الممكنة من${\displaystyle \Sigma ^{*}}$.

في علوم الحاسوب والرياضيات، اللتين لا تتعاملان عادةً مع اللغات الطبيعية ، غالبًا ما تُحذف صفة "رسمي" باعتبارها زائدة. من ناحية أخرى، يمكننا ببساطة أن نقول "لغة رسمية".${\displaystyle L}$"عندما أبجديتها${\displaystyle \Sigma }$الأمر واضح في السياق.

بينما تهتم نظرية اللغات الرسمية عادةً باللغات الرسمية التي تُوصف بقواعد نحوية معينة، فإن التعريف الفعلي لمفهوم "اللغة الرسمية" يقتصر على ما سبق ذكره: مجموعة (قد تكون غير محدودة) من سلاسل نصية محدودة الطول مُؤلَّفة من أبجدية معينة، لا أكثر ولا أقل. عمليًا، توجد لغات عديدة يمكن وصفها بقواعد، مثل اللغات المنتظمة أو اللغات الخالية من السياق . قد يكون مفهوم القواعد النحوية الرسمية أقرب إلى المفهوم البديهي لـ"اللغة"، أي اللغة التي تُوصف بقواعد نحوية. وبسبب إساءة استخدام التعريف، يُفترض غالبًا أن لغة رسمية معينة مصحوبة بقواعد نحوية رسمية تصفها.

تصف القواعد التالية لغة رسمية L على الأبجدية Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:   

• كل سلسلة غير فارغة لا تحتوي على " +" أو "=" ولا تبدأ بـ "0" موجودة في L. 
• السلسلة "0" موجودة في L. 
• تكون السلسلة التي تحتوي على "=" في L إذا وفقط إذا كان هناك "=" واحد بالضبط، وهي تفصل بين سلسلتين صالحتين من L.  
• تكون السلسلة التي تحتوي على "+" ولكن لا تحتوي على "=" ضمن L إذا وفقط إذا كان كل "+" في السلسلة يفصل بين سلسلتين صالحتين من L.  
• لا توجد سلسلة نصية في L بخلاف تلك التي تشير إليها القواعد السابقة. 

وفقًا لهذه القواعد، فإن السلسلة "23+4=555" تنتمي إلى اللغة L ، بينما السلسلة "=234=+" لا تنتمي إليها. تُعبّر هذه اللغة الرسمية عن الأعداد الطبيعية ، وعمليات الجمع الصحيحة، ومعادلات الجمع الصحيحة، لكنها تُعبّر فقط عن شكلها (بنيتها ) ، وليس عن معناها ( دلالاتها ). على سبيل المثال، لا يوجد في هذه القواعد ما يُشير إلى أن "0" تعني العدد صفر، أو أن "+" تعني الجمع، أو أن "23+4=555" خاطئة، وهكذا. 

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

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

تشمل الأسئلة النموذجية التي تُطرح حول هذه الأشكال الرسمية ما يلي:

• ما هي قدرتها التعبيرية؟ (هل يمكن للصيغة X أن تصف كل لغة يمكن للصيغة Y أن تصفها؟ وهل يمكنها وصف لغات أخرى؟)
• ما مدى سهولة التعرف عليها؟ (ما مدى صعوبة تحديد ما إذا كانت كلمة معينة تنتمي إلى لغة موصوفة بالصيغة X ؟)
• ما مدى قابليتهما للمقارنة؟ (ما مدى صعوبة تحديد ما إذا كانت لغتان، إحداهما موصوفة بالشكل X والأخرى بالشكل Y ، أو بالشكل X مرة أخرى، هما في الواقع نفس اللغة؟).

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

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

أمثلة: لنفترض${\displaystyle L_{1}}$و${\displaystyle L_{2}}$اللغات التي تستخدم أبجدية مشتركة${\displaystyle \Sigma }$.

• التسلسل​${\displaystyle L_{1}\cdot L_{2}}$يتكون من جميع السلاسل النصية التي على شكل${\displaystyle vw}$أين${\displaystyle v}$هي سلسلة من${\displaystyle L_{1}}$و${\displaystyle w}$هي سلسلة من${\displaystyle L_{2}}$.
• التقاطع​${\displaystyle L_{1}\cap L_{2}}$ل${\displaystyle L_{1}}$و${\displaystyle L_{2}}$يتكون من جميع السلاسل النصية الموجودة في كلتا اللغتين
• المكمل​${\displaystyle \neg L_{1}}$ل${\displaystyle L_{1}}$بالنسبة إلى${\displaystyle \Sigma }$يتكون من جميع السلاسل فوق${\displaystyle \Sigma }$التي ليست في${\displaystyle L_{1}}$.
• نجمة كلين : اللغة التي تتكون من جميع الكلمات التي هي عبارة عن سلاسل من صفر أو أكثر من الكلمات في اللغة الأصلية؛
• الانعكاس :
  • لنفترض أن ε هي الكلمة الفارغة، إذن${\displaystyle \varepsilon ^{R}=\varepsilon }$، و
  • لكل كلمة غير فارغة${\displaystyle w=\sigma _{1}\cdots \sigma _{n}}$(أين${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$(عناصر من أبجدية ما)، لنفترض${\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}$،
  • ثم للغة رسمية${\displaystyle L}$،${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$.
• تماثل السلاسل

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

خصائص الإغلاق لعائلات اللغات (${\displaystyle L_{1}}$عملية${\displaystyle L_{2}}$حيث كلاهما${\displaystyle L_{1}}$و${\displaystyle L_{2}}$(تنتمي إلى عائلة اللغة المحددة في العمود). بعد هوبكروفت وأولمان.

عملية		عادي	دي سي إف إل	دوري كرة القدم الكندية	الهند	سي إس إل	التكراري	يكرر
الاتحاد	${\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}$	نعم	لا	نعم	نعم	نعم	نعم	نعم
تقاطع	${\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}$	نعم	لا	لا	لا	نعم	نعم	نعم
إطراء	${\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}$	نعم	نعم	لا	لا	نعم	نعم	لا
سلسلة	${\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}$	نعم	لا	نعم	نعم	نعم	نعم	نعم
كلين ستار	${\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}$	نعم	لا	نعم	نعم	نعم	نعم	نعم
التماثل (السلسلة)${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	نعم	لا	نعم	نعم	لا	لا	نعم
التماثل الخالي من إبسيلون (للسلاسل)${\displaystyle h}$	${\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}$	نعم	لا	نعم	نعم	نعم	نعم	نعم
الاستبدال${\displaystyle \varphi }$	${\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}$	نعم	لا	نعم	نعم	نعم	لا	نعم
التماثل العكسي${\displaystyle h^{-1}}$	${\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}$	نعم	نعم	نعم	نعم	نعم	نعم	نعم
يعكس	${\displaystyle L^{R}=\{w^{R}\mid w\in L\}}$	نعم	لا	نعم	نعم	نعم	نعم	نعم
التقاطع مع لغة منتظمة${\displaystyle R}$	${\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}$	نعم	نعم	نعم	نعم	نعم	نعم	نعم

• التوافقية في الكلمات
• الطريقة الرسمية
• أحادي حر
• إطار القواعد النحوية
• قائمة الأنظمة الرسمية
• الترميز الرياضي
• السلاسل النصية (علوم الحاسوب)

• "اللغة الرسمية" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• جامعة ميريلاند ، تعريفات اللغة الرسمية، مؤرشفة بتاريخ 16 فبراير 2008 في أرشيف الإنترنت (Wayback Machine).
• جيمس باور، "ملاحظات حول نظرية اللغة الرسمية والتحليل النحوي" مؤرشف في 21 نوفمبر 2007 في Wayback Machine ، 29 نوفمبر 2002.
• مسودات بعض الفصول في "دليل نظرية اللغة الرسمية"، المجلدات 1-3، تحرير جي. روزنبرغ وأ. سالوما، دار نشر سبرينغر ، (1997):
  • ألكساندرو ماتيسكو وأرتو سالوما، "المقدمة" في المجلد الأول، الصفحات من الخامس إلى الثامن، و"اللغات الرسمية: مقدمة وملخص"، الفصل الأول في المجلد. 1، ص 1-39
  • شينغ يو، "اللغات المنتظمة"، الفصل الثاني في المجلد الأول
  • جان ميشيل أوتيبير، جان بيرستيل، لوك بواسون، "اللغات الخالية من السياق والآلات ذاتية الدفع"، الفصل 3 في المجلد 1
  • كريستيان تشوفروت وجوهاني كارهوماكي، "تركيبات الكلمات"، الفصل السادس في المجلد. 1
  • تيرو هارجو وجوهاني كارهوماكي، "التشكلات"، الفصل السابع في المجلد. 1، ص 439-510
  • جان إريك بين، "المجموعات شبه التركيبية"، الفصل 10 في المجلد 1، الصفحات 679-746
  • م. كروشيمور و سي. هانكارت، "الآلات الآلية لمطابقة الأنماط"، الفصل 9 في المجلد 2
  • دورا جياماريسي، أنطونيو ريستيفو، "اللغات ثنائية الأبعاد"، الفصل الرابع في المجلد. 3، ص 215-267