CFG لتقف علي قواعد خالية من السياق. وهو عبارة عن قواعد نحوية رسمية تُستخدم لإنشاء جميع أنماط السلاسل الممكنة في لغة رسمية معينة. يمكن تعريف القواعد النحوية الخالية من السياق G بأربعة صفوف على النحو التالي:
G = (V, T, P, S)
أين،
ز هو النحو الذي يتكون من مجموعة من قواعد الإنتاج. يتم استخدامه لإنشاء سلسلة اللغة.
ت هي المجموعة النهائية من رمز المحطة. ويشار إليه بأحرف صغيرة.
في هي المجموعة النهائية من الرمز غير الطرفي. ويشار إليه بأحرف كبيرة.
ص هي مجموعة من قواعد الإنتاج، والتي تُستخدم لاستبدال الرموز غير الطرفية (على الجانب الأيسر من الإنتاج) في سلسلة برموز طرفية أو غير طرفية أخرى (على الجانب الأيمن من الإنتاج).
جافا سكريبت تحميل البرنامج النصي
س هو رمز البداية الذي يستخدم لاشتقاق السلسلة. يمكننا استخلاص السلسلة عن طريق استبدال الطرف غير الطرفي بشكل متكرر بالجانب الأيمن من الإنتاج حتى يتم استبدال جميع العناصر غير الطرفية برموز طرفية.
مثال 1:
أنشئ CFG للغة التي تحتوي على أي عدد من الحروف a فوق المجموعة ∑= {a}.
حل:
كما نعلم التعبير العادي للغة المذكورة أعلاه هو
r.e. = a*
قاعدة الإنتاج للتعبير العادي هي كما يلي:
S → aS rule 1 S → ε rule 2
الآن إذا أردنا استخلاص سلسلة نصية 'aaaaaa'، فيمكننا أن نبدأ برموز البداية.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
هناك. = a* يمكنه إنشاء مجموعة من السلاسل {ε, a, aa, aaa,.....}. يمكن أن يكون لدينا سلسلة فارغة لأن S هو رمز البداية والقاعدة 2 تعطي S → ε.
مثال 2:
إنشاء CFG للتعبير العادي (0+1)*
حل:
نص غامق CSS
يمكن إعطاء CFG بواسطة ،
Production rule (P): S → 0S | 1S S → ε
القواعد موجودة في مزيج من 0 و 1 مع رمز البداية. بما أن (0+1)* تشير إلى {ε, 0, 1, 01, 10, 00, 11, ....}. في هذه المجموعة، ε عبارة عن سلسلة، لذا في القاعدة، يمكننا ضبط القاعدة S → ε.
مثال 3:
أنشئ CFG للغة L = حيث w € (a, b)*.
حل:
السلسلة التي يمكن إنشاؤها للغة معينة هي {aacaa، bcb، abcba، bacab، abbcbba، ....}
القواعد النحوية يمكن أن تكون:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
الآن إذا أردنا اشتقاق سلسلة 'abbcbba'، فيمكننا البدء برموز البداية.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
وبالتالي يمكن اشتقاق أي من هذا النوع من السلاسل من قواعد الإنتاج المحددة.
مثال 4:
قم ببناء CFG للغة L = aنب2nحيث ن>=1.
حل:
السلسلة التي يمكن إنشاؤها للغة معينة هي {abb, aabbbb, aaabbbbbb....}.
فرز قائمة الصفيف جافا
القواعد النحوية يمكن أن تكون:
S → aSbb | abb
الآن إذا أردنا اشتقاق سلسلة 'aabbbb'، فيمكننا البدء برموز البداية.
S → aSbb S → aabbbb