اللغات والقواعد والآلات نظرياً
في هذه السلسلة – ان شاء الله – سأشرح أهم المواضيع في منهج نظرية الحوسبة في أكثر من مقالة ولمن أراد الاطلاع أكثر فمرجعي الرئيسي هو كتاب
An Introduction to FORMAL LANGUAGES and AUTOMATA
للكاتب
PETER LINZ
المنهج مهم جداً لطلاب علوم الحاسب فهو يناقش مجموعة من المفاهيم النظرية البحتة والتي ساعدت في انشاء علوم الحاسب والخوارزميات وعلم المنطق والتي يجب على كل طالب استيعابها وفهمها .
هناك ٣ محاور رئيسية لا بد من التحدث عنها قبل أن نسترسل في شرح أنواع القواعد والآلات الموجودة .
أولاً : اللغات :
أغلب القواميس في جميع اللغات تعرف لنا اللغة بأنها نظام من التعبيرات لمجموعة من الأفكار والمفاهيم والحقائق وتضم عدداً من الرموز والقواعد لإنشاء الجمل والكلمات بشكل صحيح تحت هذه اللغة .
نبدأها بمجموعة منتهية غير فارغة نسميها آلفابت Alphabet ويرمز لها برمز سيجما ∑ ومن خلال رمز واحد من الآلفابت يمكننا تكوين كلمة String والكلمة عبارة عن سلسلة منتهية من الرموز في الآلفابت .
مثال : لدينا الآلفابت التالية
∑ = {a, b}
فيمكننا انشاء كلمة ( نرمز لها بالرمز w ) تسمى abba أو a أو ba لأنها كلمات ضمن الألفابت الموجودة ، اذاً يمكننا عمل مجموعة لانهائية من الكلمات تحت آلفابت معينة .
طول الكلمة يرمز له بالرمز |w| وهو رقم يساوي عدد الحروف في تلك الكلمة واذا كان طول الكلمة يساوي الصفر فيعني ذلك أن تلك الكلمة تسمى (ايبسلون أو لمدا ) ونرمز لها بالرمز λ .
λ|=0| .
ثانياً : القواعد :
تُعرَف القاعدة Rule عن طريق الرموز التالية
G =(V, T, S, P)
1- V : مجموعة من المتغيرات .
2- T : مجموعة من الرموز المنتهية التي ننهي بها الكلمة .
3- S : رمز البداية وهو ضمن T .
4- P : القواعد التي نتبعها في صنع أي كلمة ضمن آلفابت معينة وهي قلب وأساس أي قاعدة .
نفرض أن كل القواعد تأتي بهذا الشكل
x -> y
بحيث أن x تعني جميع المتغيرات والرموز المنتهية و y تحتوي على الرموز المنتهية والمتغيرات + الكلمة الفارغة λ .
مثال توضيحي :
G = { {S},{a,b},S,P}
و القواعد في هذه اللغة P
S -> aSb
S -> λ
أمثلة على الكلمات التي يمكننا اشتقاقها من هذه القاعدة
ab , aabb , aaabbb وهكذا ، اذاً اللغة الخاصة بهذا القاعدة عباره عن مجموعة من a تتبعها مجموعة من b بنفس العدد .
يمكننا كتابة اللغة بهذه الصيغة :
ثالثاً : الآلات :
الآلات Automata هي عبارة عن نموذج نظري للكمبيوترات الرقمية ، كل آلة لها ميكانيكا خاصة لقراءة المدخلات لكن لا تغيرها ويمكنها أيضاً تحديد نهاية وبداية كل كلمة أو مُدخل ويمكن أن يكون لها أجهزة تخزين وتحتوي على مجموعة من وحدات التحكم التي تتغير حالتها ومجموعة من دوال التغير المرتبطة بالمدخل والحالة الحالية للمدخل .
بإذن الله في المقالات التالية سوف نناقش ٤ أنواع من الآلات وطريقة عملها والقواعد التي تقبلها ومايخصها بشكل مخصص .
لايوجد لديك حساب في عالم البرمجة؟
تحب تنضم لعالم البرمجة؟ وتنشئ عالمك الخاص، تنشر المقالات، الدورات، تشارك المبرمجين وتساعد الآخرين، اشترك الآن بخطوات يسيرة !