الرموز المنتهية والغير منتهية

في علوم الحاسب , الرموز المنتهية والغير منتهية هي عبارة عن عناصر مفردة تستخدم في تحديد قاعدة التوليد التي تشكل القاعدة الرسمية. الرموز المنتهية هي عبارة عن رموز أولية للغة المعرفة بواسطة القاعدة الرسمية. الرموز الغير منتهية ( أو المتغيرات النحوية) يتم استبدالها بمجموعه من الرموز المنتهية طبقاً قاعدة التوليد .الرموز المنتهية والغير المنتهية لقواعد لغة معينه هي عبارة عن مجموعتين منفصلتين.

المحتويات
- الرموز المنتهية
- الرموز الغير المنتهية
- قواعد التوليد
- أمثلة
- المراجع

الرموز المنتهية :-

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

الرمز ר يمكن أن يصبح ди
الرمز ר يمكن أن يصبح д

هنا д هو عبارة عن رمز منتهي لأنه لا توجد قاعدة ممكن أن تستبدله ب أي رمز آخر. ومن ناحية أخرى هنالك قاعدتين لرمز Д يتم استبدالها به , فبالتالي ר هو عبارة عن رمز غير منتهي . اللغة الرسمية معرفه أو تم توليدها بواسطة قواعد معينة من مجموعه من المتسلسلات التي يمكن تولدها من قاعدة معينه والتي تتكون من رموز منتهية فقط .

الرموز الغير منتهية :-

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

قواعد التوليد :-

القواعد تحدد بواسطة قواعد التوليد (أو فقط عمليات التوليد ) التي تقوم بتحديد رموز يتم استبدالها برموز أخرى , هذه القواعد يمكن استخدامها في توليد متسلسلات , أو فقط استبدالهم برموز أخرى , قد يتم استخدامها في أنشاء متسلسلات أو تحليلها . كل قاعدة لها رأس , أو جانب أيسر والذي يتكون من مجوعه من المتسلسلات التي يمكن أبدالها , و جسم أو الجانب الأيمن والذي يتكون من مجموعه من المتسلسلات التي تحل محلها.

القاعدة غالبا تكتب على هذه الصيغة

   الجسم → الراس  . ″_{هذه تقرأ بهذه الصيغة الرأس يؤدي أو يؤول الى الجسم} ″

على سبيل المثال هذه القاعدة :

a→ b

و تنص القاعدة أن a يمكن أن يستبدل مكانها b .

طرح هذا الطابع الكلاسيكي القاعدة الرسمية من قبل نعوم تشومسكي في عام 1950 ^[1]^[2], القاعدة G تتكون من :

$\mathrm {N}$ هي مجموعة عناصر محدده غير منتهية .
$\Sigma$ هي مجموعة عناصر محددة منتهية اتكون مستقلة عن $\mathrm {N}$ .

$\mathrm {P}$ هي مجموعة عناصر محددة مكونة من قواعد التوليد , كل قاعدة تكون على الشكل :

                                    $(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$

حيث أن **$$ هي عبارة عن مشغل نجمة كلين و $\cup$ دليل على مجموعه الاتحاد , إذاً $(\Sigma \cup N)^{}$ , $*$ تدل على صفر أو أكثر من الرموز أي لا يوجد رمز أو تكرار الرموز و $\mathrm {N}$** تدل على الرموز الغير منتهية . كل قاعدة توليد متصلة بمجموعه من المتسلسلات المكونة من رمز إلى آخر , حيث أن السلسلة الأولى تحتوى على الأقل رمز واحد غير منتهي .في حالة أن الجسم يتكون من سلسلة فارغة هذا يعني أنها لا تحتوى على أي رمز , قد تكون مرتبطة بمدلول خاص كمثل ( $\Lambda$ , $e$ أو $\epsilon$ ) لتجنب أي ارتباك أو تشويش أثناء الاشتقاق أو التبديل.

تمييز رمز $S\in N$ والتي تدل أنها رمز البداية .

يتم تعريف القاعدة الرسمية على أنها رباعية مرتبة $<N,\Sigma ,P,S>$ غالبا ما يمسى مثل هذه القاعدة الرسمية ب أعادة كتابة النظام أو بناء عبارة نحوية في الأدب ^[3] ^[4].

الأمثلة:-

على سبيل المثال : ب أتباع تمثيل الإعداد ( والتي ممكن أن تكون ب أشارة ) يتم التعبير عنه بصيغة باكوس نور:

<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<integer> ::= ['-'] <digit> {<digit>}

في هذا المثال الرموز هي (0,1,2,3,4,5,6,7,8,9,-) هي عبارة عن رموز منتهية , أما <digit> و <integer> هي عبارة عن الرموز الغير منتهية .

ملاحظة : هذا المثال يدعم متسلسلة مع تبدأ أصفار مثل "0056 " أو "000" , ب الإضافة إلى أصفار السالبة مثل "0 -" و مثل "00000 -".

مثال آخر : →

S → cAd

A → a|ab

في هذا المثال , الرموز المنتهية هي "a,b,c,d " و الموز الغير منتهية هي "S , A" .

المراجع

^[1]

^[2]

^[3]

^[4]

^ ^ا ^ب Chomsky, Noam (1956). "Three Models for the Description of Language". IRE Transactions on Information Theory. 2 (2): 113–123. doi:10.1109/TIT.1956.1056813 .
^ ^ا ^ب Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton.
^ ^ا ^ب Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. pp. 8–9. ISBN 0-7204-2506-9.
^ ^ا ^ب Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. p. 13. ISBN 0-201-02955-3.

[:0-1] ا ^ب Chomsky, Noam (1956). "Three Models for the Description of Language". IRE Transactions on Information Theory. 2 (2): 113–123. doi:10.1109/TIT.1956.1056813 .

[:1-2] ا ^ب Chomsky, Noam (1957). Syntactic Structures. The Hague: Mouton.

[:2-3] ا ^ب Ginsburg, Seymour (1975). Algebraic and automata theoretic properties of formal languages. North-Holland. pp. 8–9. ISBN 0-7204-2506-9.

[:3-4] ا ^ب Harrison, Michael A. (1978). Introduction to Formal Language Theory. Reading, Mass.: Addison-Wesley Publishing Company. p. 13. ISBN 0-201-02955-3.

[1]

[2]

[3]

[4]

مستخدم:Hessa-SH/ملعب

الرموز المنتهية والغير منتهية

الرموز المنتهية :-

الرموز الغير منتهية :-

قواعد التوليد :-

القاعدة غالبا تكتب على هذه الصيغة

على سبيل المثال هذه القاعدة :

a→ b

و تنص القاعدة أن a يمكن أن يستبدل مكانها b .

طرح هذا الطابع الكلاسيكي القاعدة الرسمية من قبل نعوم تشومسكي في عام 1950 [1][2], القاعدة G تتكون من :

الأمثلة:-

على سبيل المثال : ب أتباع تمثيل الإعداد ( والتي ممكن أن تكون ب أشارة ) يتم التعبير عنه بصيغة باكوس نور:

في هذا المثال الرموز هي (0,1,2,3,4,5,6,7,8,9,-) هي عبارة عن رموز منتهية , أما <digit> و <integer> هي عبارة عن الرموز الغير منتهية .

ملاحظة : هذا المثال يدعم متسلسلة مع تبدأ أصفار مثل "0056 " أو "000" , ب الإضافة إلى أصفار السالبة مثل "0 -" و مثل "00000 -".

مثال آخر : →

في هذا المثال , الرموز المنتهية هي "a,b,c,d " و الموز الغير منتهية هي "S , A" .

المراجع

طرح هذا الطابع الكلاسيكي القاعدة الرسمية من قبل نعوم تشومسكي في عام 1950 ^[1]^[2], القاعدة G تتكون من :