اللغات العادية وآلات الحالة المحدودة. اللغة العادية اللغات العادية وآلات الحالة المحدودة

مجموعات عاديةوالتعبيرات العادية

مجموعات عادية

في هذا القسم، سننظر في فئة من مجموعات السلاسل عبر قاموس محدود، والتي يسهل وصفها بصيغ من نوع ما. وتسمى هذه المجموعات العادية.

التعريف 1.يتركالخامس 1 والخامس 2 - العديد من السلاسل. دعونا نحدد ثلاث عملياتعلى هذه المجموعات.

الاتحاد: V 1 V 2 =(|   V 1 ) أو   V 2 .

التسلسل (المنتج، اللصق): Vl V2 = (|  V 1 ,  V 2 ) عادةً ما يتم حذف علامة عملية التسلسل.

مثال: V، = (abc، ba)،V 2 = (b، cb). V1V2 = (abcb، abccb، باب، bacb).

دعونا نشير بواسطة V n منتج n مجموعات V:V n =VV...V,V° =() (هنا  سلسلة فارغة).

مثال: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. التكرار: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

مثال: V = (a، bc)، V* = (، a، bc، aa، abc، bcbc، bca، aaa، aabc،...).

التعريف 4.13.فئة المجموعات العادية عبر قاموس محدودالخامس يُعرِّفغني عن مثل هذا:

الاتحاد ST؛

سلسلة ST؛

التكرار S* و T*.

5. إذا لم يكن من الممكن إنشاء مجموعة بعدد محدود من تطبيقات القواعد 1-4، فهي غير منتظمة.

أمثلة على المجموعات العادية: (ab, ba)* (aa); (ب)((ج)(د، أب)*). أمثلة على المجموعات غير المنتظمة: (a n b n | n > 0); ( | في السلسلة  عدد مرات ظهور الرمزين a وb متطابقان).

التعبيرات العادية

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

التعريف 2.فئة التعبير العادي على القاموس المحدودالخامس يُعرِّفغني عن مثل هذا:

مجموعهم R1+R2؛

منتجهم R1R2؛

تكرارهم R1* وR2*.

4. إذا لم يتم إنشاء التعبير من خلال تطبيق القواعد 1-3 بشكل محدود، فهو غير منتظم.

يمكن حذف رمز العمل. لتقليل عدد الأقواس، كما هو الحال في أي علم جبر، يتم استخدام أولويات العملية: التكرار له الأولوية القصوى؛ العمل له أولوية أقل؛ الإضافة لها الأولوية الدنيا.

أمثلة على التعبيرات النمطية: ab + bа*; (أأ)*ب+(ج+داب)*.

من الواضح أن المجموعات العادية والتعبيرات العادية متقاربة جدًا. لكنها تمثل كيانات مختلفة: المجموعة العادية هي مجموعة من السلاسل (في الحالة العامة لا نهاية لها)، و التعبير العادي هوصيغة توضح بشكل تخطيطي كيفية إنشاء المجموعة العادية المقابلة باستخدام العمليات المذكورة أعلاه(وهذه الصيغة محدودة).

اجعل R^ مجموعة عادية تقابل التعبير العادي R. ثم:

وبالتالي، فإن التعبير العادي هو صيغة محدودة تحدد عددًا لا حصر له من السلاسل، أي اللغة.

دعونا نلقي نظرة على أمثلة التعبيرات العادية واللغات المقابلة لها.

تعبير عادي	اللغة المقابلة
	جميع السلاسل التي تبدأ بـ b متبوعة بعدد عشوائي من الأحرف a
	جميع سلاسل a وb تحتوي على تكرارين بالضبط لـ b
	جميع سلاسل a وb التي يظهر فيها الرمز b في أزواج فقط
(أ+ب)*(أأ+ب)(أ+ب)*	جميع سلاسل a وb تحتوي على زوج واحد على الأقل من المتجاورين a أو b
(0+1)*11001(0+1)*	جميع السلاسل 0 و 1 تحتوي على السلسلة الفرعية 11001
	جميع سلاسل a وb، التي تبدأ بـ a وتنتهي بـ b

من الواضح أن مجموعة السلاسل تكون منتظمة إذا وفقط إذا كان من الممكن تمثيلها بتعبير عادي. ومع ذلك، يمكن تمثيل نفس مجموعة السلاسل بتعبيرات عادية مختلفة، على سبيل المثال، مجموعة من السلاسل التي تتكون من رموز a وتحتوي على اثنين على الأقل a يمكن تمثيلها بالتعبيرات: aa*a؛ أ*أأ*; آآ*; أ*أأ*أأ*، الخ.

التعريف 3.اثنين من التعبيرات العاديةر1 و R2 تسمى ما يعادل (المشار إليهارل = ر2) ثم وفقط عندمار1 ^ = ر2 ^ .

وبالتالي، aa*a = a*aaa* = aaa* = a*aa*aa*. السؤال الذي يطرح نفسه هو كيفية تحديد تكافؤ تعبيرين عاديين.

نظرية1 . لأية تعبيرات عاديةر، س وت عدل:

يمكن إثبات هذه العلاقات عن طريق التحقق من تساوي مجموعات السلاسل المقابلة. ويمكن استخدامها لتبسيط التعبيرات العادية. على سبيل المثال: ب (ب + أأ*ب) = ب (ب + أأ*ب) = ب ( + أأ*) ب = با*ب. ومن ثم فإن b (b + aa*b) = ba*b، وهو أمر غير واضح.

نظرية كلين

التعبيرات العادية هي الصيغ النهائية التي تحدد اللغات العادية. لكن آلات الحالة المحدودة لها أيضًا خاصية مماثلة، فهي تحدد اللغات أيضًا. السؤال الذي يطرح نفسه: كيف ترتبط فئات اللغات المحددة بواسطة آلات الحالة المحدودة والتعبيرات العادية ببعضها البعض؟ دعونا نشير والعديد من اللغات التلقائية، R هي مجموعة من اللغات العادية. أثبت عالم الرياضيات الأمريكي ستيفن كلين النظرية التالية.

نظرية2 . (نظرية كلين). تتطابق فئات المجموعات العادية ولغات الأوتوماتا، أي أ = ر .

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

دعونا نقدم نموذج الرسم البياني الانتقالي كتعميم لنموذج الإنسان المحدود. يحتوي الرسم البياني الانتقالي على عدد أولي واحد وتعسفي من القمم النهائية، ويتم تمييز الحواف الموجهة، على عكس الإنسان الآلي المحدود، ليس بالرموز، ولكن بالتعبيرات العادية. الرسم البياني الانتقالي يعترف بسلسلة a if أينتمي إلى مجموعة من السلاسل، الموصوفة بمنتج التعبيرات النمطية R 1 R 2 ...R n ، والتي تحدد المسار من الرأس الأولي إلى أحد القمم النهائية. تشكل مجموعة السلاسل التي يسمح بها الرسم البياني الانتقالي اللغة التي يسمح بها.

أرز. 1. الرسم البياني الانتقالي

في التين. يوضح الشكل 1 رسمًا بيانيًا انتقاليًا يسمح، على سبيل المثال، بسلسلة abbca، نظرًا لأن المسار s->r->p->s->r->q، الذي يؤدي إلى الحالة النهائية q، يتميز بسلسلة من التعبيرات العادية ab* c*a. تعد آلة الحالة المحدودة حالة خاصة من الرسم البياني الانتقالي، وبالتالي فإن جميع اللغات التي تقبلها أجهزة الحالة يتم دعمها أيضًا من خلال الرسوم البيانية الانتقالية.

النظرية 3.كل لغة آلية هي مجموعة منتظمة، أ ر.

دليل. الرسم البياني الانتقالي ذو قمة أولية وأخرى نهائية، حيث يتم تسمية الحافة الوحيدة من الرأس الأولي إلى القمة النهائية بتعبير عادي R، ويعترف باللغة R^ (الشكل 1).

أرز. 2. الرسم البياني الانتقالي الذي يعترف باللغة العادية FT

دعونا الآن نثبت أن كل لغة آلية هي مجموعة منتظمة عن طريق تقليل أي رسم بياني انتقالي دون تغيير اللغة التي تسمح بها إلى شكل مكافئ (الشكل 2).

يمكن دائمًا تمثيل أي إنسان آلي محدود وأي رسم بياني انتقالي في شكل طبيعي، حيث يوجد قمة أولية واحدة فقط مع حواف صادرة فقط وقمة نهائية واحدة فقط مع حواف واردة فقط (الشكل 3).

أرز. 3. رسم بياني انتقالي ذو قمة أولية وأخرى نهائية

من خلال الرسم البياني الانتقالي المقدم في شكل عادي، يمكن إجراء عمليتين للتصغير - تقليل الحافة وتقليل قمة الرأس - مع الحفاظ على اللغة التي يسمح بها هذا الرسم البياني الانتقالي:

أ) تصغير الأضلاع:

ب ) تخفيض قمة الرأس (يتم إجراء الاستبدال لكل مسار يمر عبر قمة الرأس p، متبوعًا بالتخلص منه باعتباره حالة لا يمكن الوصول إليها):

من الواضح أن كل عملية اختزال لا تغير اللغة التي يتعرف عليها الرسم البياني الانتقالي، ولكنها تقلل إما من عدد الحواف أو عدد القمم، وفي النهاية ستؤدي التخفيضات إلى إحضار الرسم البياني الانتقالي إلى الشكل الموضح في الشكل. 2. تم إثبات النظرية: كل لغة آلية هي مجموعة منتظمة.

مثال

دع الآلة المحدودة A تعطى:

نقوم ببناء رسم بياني انتقالي مكافئ في شكل طبيعي.

تخفيض قمة الرأس 3:

تصغير الأقواس وتطبيق القاعدة R = R:

تخفيض قمة الرأس 2:

تخفيض القوس والقمة 1:

وبالتالي، فإن اللغة التي يتعرف عليها الإنسان A يتم الحصول عليها من خلال التعبير العادي: R A = b+(a+bb)(b+ab)*a.

دعونا نثبت نظرية كلين في الاتجاه الآخر.

النظرية 2.كل مجموعة عادية هي لغة آلية: ر أ.

دليل.دعونا نبين أنه لكل تعبير عادي R، يمكن إنشاء آلة آلية محدودة A r (ربما غير حتمية) تتعرف على اللغة المحددة بواسطة R. وسوف نقوم بتعريف هذه الآلات بشكل متكرر.

(يتم الجمع بين الحالتين الأولية والنهائية لـ A).

مثال(استمرار)

القواعد النحوية العادية، والأتمتة المحدودة، والمجموعات العادية (والتعبيرات العادية التي تمثلها) هي ثلاث طرق مختلفة لتحديد اللغات العادية.

إفادة

تعتبر اللغة PM إذا وفقط إذا تم تحديدها بواسطة قواعد نحوية خطية يسارية (خطية يمينية). يمكن تعريف اللغة بقواعد نحوية خطية يسارية (خطية يمينية) إذا كانت مجموعة عادية فقط.

تعتبر اللغة PM إذا وفقط إذا تم تحديدها بواسطة آلة الحالة المحدودة. يتم التعرف على اللغة بواسطة آلة الحالة إذا وفقط إذا كانت PM.

كل هذه الطرق الثلاثة متكافئة. هناك خوارزميات تسمح للغة محددة بإحدى هذه الطرق ببناء طريقة أخرى تحدد نفس اللغة. يتوفر وصف تفصيلي لهذه الخوارزميات في الأدبيات (انظر القائمة).

على سبيل المثال، للعثور على تعبير منتظم للغة محددة بواسطة القواعد الخطية اليمنى، من الضروري إنشاء وحل نظام من المعادلات ذات المعاملات المنتظمة.

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

لإنشاء مرجع مصدق (CA) استنادًا إلى قواعد نحوية منتظمة معروفة، يجب اختزاله إلى نموذج آلي. مجموعة حالات الآلة سوف تتوافق مع مجموعة الرموز غير الطرفية للقواعد. 2.3.2 خصائص اللغات العادية

تسمى المجموعة مغلقة في ظل بعض العمليات إذا تم الحصول على عنصر جديد ينتمي إلى نفس المجموعة نتيجة لتنفيذ هذه العملية على أي من عناصرها.

يتم إغلاق المجموعات العادية بموجب عمليات التقاطع والاتحاد والإضافة والتكرار والتسلسل وتغيير أسماء الرموز واستبدال السلاسل بالرموز.

بالنسبة للغات العادية، يمكن حل العديد من المشكلات التي لا يمكن حلها بالنسبة لأنواع أخرى من اللغات. على سبيل المثال، المشاكل التالية قابلة للحل بغض النظر عن كيفية تحديد اللغة:

مشكلة التكافؤ: بالنظر إلى لغتين عاديتين L 1 (V) وL 2 (V). من الضروري تحديد ما إذا كانت متكافئة.

مشكلة السلسلة التي تنتمي إلى اللغة. بالنظر إلى لغة عادية L(V)، سلسلة من الرموز V * . نحن بحاجة إلى التحقق مما إذا كانت هذه السلسلة تنتمي إلى اللغة.

مشكلة الفراغ اللغوي. نظرا للغة العادية L(V). ومن الضروري التحقق مما إذا كانت هذه اللغة فارغة، أي. ابحث عن سلسلة واحدة على الأقل، L(V).

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

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

رسميا، يتم كتابة ليما على النحو التالي. إذا تم إعطاء لغة L، فإن الثابت p>0 هو أنه إذا تم إعطاء L وp، فيمكن كتابة السلسلة بالشكل حيث 0

مثال. خذ بعين الاعتبار اللغة L=(a n b n n>0). دعونا نثبت أنه ليس من المعتاد استخدام المصطلح المتعلق بانتشار اللغات.

فلتكن هذه اللغة منتظمة، فلا بد أن يكون لها لفظ التوسع. لنأخذ سلسلة من هذه اللغة = a n b n ونكتبها في النموذج. إذا كان a + أو b + فإن السلسلة i لا تنتمي إلى اللغة لأي i مما يخالف شروط الليما. إذا كانت a + b + فإن السلسلة 2 أيضًا لا تنتمي إلى اللغة L. لقد حصلنا على تناقض، وبالتالي فإن اللغة ليست منتظمة.

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

موضوع آخر مهم للدراسة في هذه الدورة هو لغة رسمية 1 – مجموعة تعسفية من الكلمات من بعض الحروف الأبجدية. ترجع أهمية اللغات الرسمية لعلوم الكمبيوتر النظرية إلى حقيقة أن نموذج البيانات الأبسط والأكثر ملاءمة المستخدم في برامج الكمبيوتر هو تسلسل محدود، كل عنصر منه مأخوذ من مجموعة محدودة محددة مسبقًا. نظرًا لأن اللغات الرسمية المستخدمة في التطبيقات عادةً ما تكون لا نهائية، فهناك حاجة إلى طريقة لوصف اللغة الرسمية بطريقة محدودة. في هذه الدورة سوف ندرس 3 وسائل كلاسيكية لهذا الوصف: الرشاشات, التعبيرات العاديةو القواعد التوليدية.

مقدمة

1. المفاهيم الأساسية لنظرية اللغات الرسمية

النظر في مجموعة محدودة غير فارغة أمكونة من حروف ( أ 1 , …, أ ك). سنطالب أ الأبجدية ، ورموزها هي حروف . يسمى أي تسلسل محدود من حروف هذه الأبجدية في كلمة واحدة (سلسلة أو خط ): ث=أ 1 أ 2 …أ ن- كلمة ( أ أنا أ), |ث| - طول الكلمة (عدد الحروف التي تتكون منها الكلمة، مع تكرار كل حرف عدة مرات كما ورد فيه ث). عبر | ث| بتشير إلى عدد مرات ظهور الرمز بلكل كلمة ث.

تسلسل لا نهائي من الحروف الأبجدية أمُسَمًّى com.superword - كلمة خارقة مكونة من عدد لا نهائي من الحروف أ. فارغ هي كلمة لا تحتوي على حرف واحد. ويرمز له بـ . من الواضح ||=0.

- العديد من الكلمات الأبجدية أطول ن. مجموعة من كل الكلمات الأبجدية أ(بما في ذلك الكلمات الفائقة) يشار إليها أ*. هذه المجموعة قابلة للعد لأنها اتحاد عدد لا يحصى من المجموعات المحدودة
. مجموعة جميع الكلمات غير الفارغة في الأبجدية أيُشار إليه بـ أ+ . لو أ={أ)، الذي - التي أ*={أ)* سيتم الإشارة إليه بواسطة أ*.

أي مجموعة فرعية
مُسَمًّى لسان (لغة رسمية ) فوق الأبجدية أ.

لو سو ذ- كلمات اللغة
، ثم الكلمة xy(نتيجة إسناد الكلمة فيفي نهاية الكلمة X) يسمى سلسلة (التشبث , عمل ) كلمات Xو في.
(نلنأخذها مرة واحدة X). هيا نضع
.

يقولون أن الكلمة X – كلمة فرعية كلمات في، لو ذ=uxvلبعض الكلمات شو الخامس. جميع الكلمات الفرعية للكلمات في اللغة
استمارة العديد من الكلمات الفرعية لغة ل، والذي يشار إليه بواسطة Subw( ل).

أمثلة. 1. بكالوريوس 3 =باا,
- هذه الكلمة لها كلمات فرعية أب, ابا, بكالوريوسوما إلى ذلك وهلم جرا.

2. كثير ( أ, أب) - اللغة (النهائية) فوق الأبجدية ( أ, ب}.

3. الكثير
هي لغة فوق الأبجدية ( أ, ب). هذه اللغة لا نهاية لها، فهي تحتوي على كلمات ب, بكالوريوس, ابا, هيئة المطارات البريطانية, أبا, باا, aabaa, abaaإلخ.

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

يترك ,
. ثم تسمى اللغة سلسلة (التشبث , عمل ) اللغات و . حيث
,
(نمرات) إذا ن>0.

أمثلة. 1. إذا
,
،الذي - التي .

2. إذا كان L = (0، 01)، إذن
.

تكرار لغة لتسمى اللغة
(وتسمى هذه العملية أيضًا النجمة كلين ). لغة
مُسَمًّى التكرار الإيجابي لغة ل.

مثال. لو أ={أ, ب) و ل={أأ, أب, بكالوريوس, ب)، الذي - التي
.

بالاستئناف أو في صورة مرآة كلمات ثالكلمة تسمى ث ر، فيها حروف الكلمة ثاذهب بترتيب عكسي. على سبيل المثال، إذا ث=البكالوريا، الذي - التي

يترك
. ثم اللسان
مُسَمًّى جاذبية لغة ل.

سوف نسمي كل بداية كلمة بادئة ، وكل نهاية كلمة - لاحقة . على سبيل المثال، إذا ذ=الخامس عشر، الذي - التي X- بادئة الكلمة في(تعيين - X[ذ)، أ الخامس- لاحقة الكلمة في(تعيين - الخامس]ذ). من الواضح أن الكلمة الفارغة هي بادئة ولاحقة لأي كلمة. جميع بادئات الكلمات في اللغة
استمارة العديد من البادئات من هذه اللغة: Pref( ل)
. مشابهة لـ سوف( ل)
-م سكين اللواحق لغة
.

إذا كانت اللغة لبحيث لا توجد كلمة لليست بادئة (لاحقة) لأي كلمة أخرى ل، ثم يقولون ذلك للديه بادئة (لاحقة) ملكية .

يترك أ 1 و أ 2 – الحروف الهجائية . إذا عرض F:
يستوفي الشرط لجميع الكلمات
و
، ثم رسم الخرائط Fمُسَمًّى التماثل .

ملحوظات. 1. يمكن إثبات أنه إذا Fهو التماثل، إذن
.

2. لا تعتبر التماثلات دائمًا اعتراضات، ولكن يتم تحديد كل تماثل بشكل فريد من خلال معانيها في الكلمات المكونة من حرف واحد.

3. تطبيق التشبيه على اللغة ل، نحصل على لغة أخرى F(ل).

لو F:
- التماثل،
و
، ثم من خلال F(ل 1) يشار إلى اللغة
، ومن خلال
يشار إلى اللغة
والعرض نفسه
مُسَمًّى انقلاب التماثل .

أمثلة. 1. لنفترض أننا نريد استبدال كل تكرار للحرف 0 في السلسلة بالحرف أ، وكل تواجد للرقم 1 قيد التشغيل ب. ثم يمكننا تحديد التماثل Fلذا
و
. لو
، الذي - التي
.

2. دع Fهو التماثل الذي
و
. ثم
و
.

نبدأ في هذا الفصل بعرض عناصر نظرية اللغات الشكلية.

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

هناك ثلاثة جوانب رئيسية يجب وضعها في الاعتبار عند تعلم اللغات.

اول واحد هو بناء جملة اللغة . اللغة هي نوع من مجموعة "الكلمات"، حيث تكون "الكلمة" عبارة عن تسلسل محدود معين من "الحروف" - رموز لبعض الأبجدية الثابتة مسبقًا. يمكن فهم المصطلحين "حرف" و"كلمة" بطرق مختلفة (سيتم تقديم التعريف الرياضي لهذه المصطلحات أدناه). وبالتالي، يمكن أن تكون "الحروف" في الواقع حروف أبجدية لبعض اللغات الطبيعية أو الرسمية، على سبيل المثال، اللغة الروسية أو لغة البرمجة باسكال. عندها ستكون "الكلمات" عبارة عن تسلسلات محدودة من "الحروف": تمساح، " عدد صحيح". تسمى هذه الكلمات "Lexemes". لكن "الحرف" يمكن أن يكون "كلمة" ("Lexeme") ككل. ثم "الكلمات" هي جمل من لغة طبيعية أو برامج لغة برمجة. إذا كانت بعض المجموعات من "الحروف" ثابتة، فلن تكون كل متوالية منها "كلمة"، أي إكسيمًا للغة معينة، بل فقط متوالية تخضع لقواعد معينة. كلمة "krykadil" ليست معجمًا باللغة الروسية، وكلمة "iff" ليست معجمًا بلغة باسكال. الجملة "أنا أحبك" ليست جملة صحيحة باللغة الروسية، تمامًا كما أن التدوين "x:= =t" ليس عامل تعيين باسكال مكتوبًا بشكل صحيح. بناء الجملة* للغة هو نظام من القواعد التي بموجبها يمكن للمرء بناء تسلسلات "صحيحة" من "الحروف". تتميز كل كلمة في اللغة ببنية معينة خاصة بتلك اللغة المعينة. ومن ثم فمن الضروري، من ناحية، تطوير آليات لتعداد أو توليد كلمات ذات بنية معينة، ومن ناحية أخرى، آليات للتحقق من أن كلمة معينة تنتمي إلى لغة معينة. بادئ ذي بدء، هذه الآليات هي التي تدرسها النظرية الكلاسيكية للغات الرسمية.

الجانب الثاني- دلالات اللغة . تتضمن علم الدلالة ** ربط كلمات لغة ما "بمعنى" معين. على سبيل المثال، عند كتابة صيغة رياضية، يجب علينا اتباع قواعد نحوية معينة (وضع الأقواس، تهجئة الرموز، ترتيب الرموز، وما إلى ذلك). )، ولكن، بالإضافة إلى ذلك، فإن الصيغة لها معنى محدد للغاية، فهذا يعني شيئا ما.

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

* تأتي كلمة "بناء الجملة" من الكلمة اليونانية القديمة "syn" - "معًا" و "سيارات الأجرة" - "النظام والهيكل". وبالتالي، يمكن فهم بناء الجملة على أنه "تكوين".

** من الكلمات اليونانية القديمة "sema" - "علامة، فأل" و"semanticos" - "تدل".

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

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

• الأبجدية، الكلمة، اللغة

• النحو التوليدي

  كما سبقت الإشارة، فإن النظرية الكلاسيكية للغات الرسمية تدرس في المقام الأول تركيب اللغة. يقدم نموذجًا رياضيًا لبناء الجملة يصف آليات إنشاء السلاسل "جيدة التكوين" والتعرف عليها. وفي هذا القسم سننظر إلى أول هذه الآليات.

نحن نعرف عمليات الجمع بين اللغات. دعونا نحدد عمليات التسلسل والتكرار (تسمى أحيانًا إغلاق كلين).

دع L 1 و L 2 هما لغتان في الأبجدية

ثم أي. تسلسل اللغةيتكون من تسلسل جميع كلمات اللغة الأولى مع جميع كلمات اللغة الثانية. على وجه الخصوص، إذا، ثم، وإذا، ثم.

دعونا نقدم تدوينًا لـ "درجات" اللغة L:

وبالتالي، L i يشمل جميع الكلمات التي يمكن تقسيمها إلى كلمات متتالية من L .

التكرار (L)* للغة L يتكون من جميع الكلمات التي يمكن تقسيمها إلى عدة كلمات متتالية من L:

ويمكن تمثيلها باستخدام الدرجات:

غالبًا ما يكون من المناسب التفكير في تكرار "مقطوع" للغة، والذي لا يحتوي على الكلمة الفارغة إذا لم تكن موجودة في اللغة: . هذه ليست عملية جديدة، ولكنها مجرد اختصار مناسب للتعبير.

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

ويقدم الجدول التالي تعريفا استقرائيا رسميا التعبيرات العاديةعلى الأبجدية واللغات التي تمثلها.

التعبير ص	اللغة لام ص
	ل ل =(أ)
دع r 1 و r 2 يكونان	L r1 و L r2 -ممثل
التعبيرات العادية.	لهم اللغات.
ثم التعبيرات التالية
منتظمة	وتمثيل اللغات:
ص=(ص 1 + ص 2)
ص = (ص 1 دائرة 2)
ص=(ص 1) *	ل ص = ل ر1 ​​*

عند التسجيل التعبيرات العاديةسنحذف علامة التسلسل ونفترض أن العملية * لها أولوية أعلى من التسلسل و+، وأن التسلسل له أولوية أعلى من +. سيسمح هذا بحذف العديد من الأقواس. على سبيل المثال، يمكن كتابتها كـ 10(1 * + 0) .

التعريف 5.1. اثنين التعبيرات العاديةيقال أن r وp متكافئان إذا كانت اللغات التي يمثلونها هي نفسها، أي. ل ص = ل ص . في هذه الحالة نكتب r = p.

من السهل التحقق، على سبيل المثال، مما يلي خصائص العاديةعمليات:

• ص + ص= ص+ ص (إبدالية الاتحاد)،
• (r+p) +q = r + (p+q) (ترابط الاتحاد)،
• (ص ع) ف = ص (ف ف) (ترابط التسلسل)،
• (ص *) * = ص * (عجز التكرار)،
• (ص +ع) ف = ر ف + pq(التوزيعية).

مثال 5.1. دعونا نثبت كمثال المساواة غير الواضحة: (r + p) * = (r * p *) *.

لتكن L 1 هي اللغة الممثلة في جانبها الأيسر، وL 2 في جانبها الأيمن. الكلمة الفارغة تنتمي إلى كلتا اللغتين. إذا كانت الكلمة غير فارغة، فمن خلال تعريف التكرار يمكن تمثيلها على أنها سلسلة من الكلمات الفرعية التي تنتمي إلى اللغة. لكن هذه اللغة هي مجموعة فرعية من اللغة L"=L r * L p * (لماذا؟). لذلك . على العكس من ذلك، إذا كانت الكلمة، فيمكن تمثيلها كسلسلة من الكلمات الفرعية التي تنتمي إلى اللغة L". كل كلمة من هذه الكلمات الفرعية v يمكن تمثيلها في النموذج v= v 1 1 ... v k 1 v 1 2 ... v l 2، حيث بالنسبة للجميع i=1، ... ، k هي كلمة فرعية وبالنسبة للجميع j=1، ... ، l هي كلمة فرعية (من الممكن أن تكون k أو l 0). ولكن هذا يعني أن w عبارة عن سلسلة من الكلمات الفرعية، كل منها ينتمي إلى، وبالتالي، .