الفصل الثالث
مقدمة
التعبير المنتظم
التعبير المنتظم وآلة الحالات_المنتهية
طريقة المسار ج[
تحويل م017 الىخ 01117
3 مبداً برج الحمام
3 التعريف الشكلي لمبداً الضخ
اسئلة الفصل الثالث
الفصل الرابع
مقدمة
القواعد
تصميم القواعد حرة السياق
كيفية صياغة قواعد للغة منتظمة
الإعراب
4 شجرة الإعراب
4 الغموض
اصيغة تشومسكي أ!
صيغة باكوس- نور
4 القواعد النحوية والاشتقاق
4 استعمال شجرة الإعراب
اسئلة الفصل الرابع

الفصل الخامس
مقدمة
تقنيات تصميم آله تورنك
اسئلة الفصل الخامس
المصادر

الفصل الثاني

2 مقدمة
تمثل نظرية التشغيل الذاتي 2:101010848 07 078017 احد فروع علم الحاسوب النظرية
المثير أت جذور هذا الفرع خلال القرن العشرين عندما بدا علماء الرياضيات؛ نظرياء
تطوير آلات تحاكي بعض الصفات لدى الانسان في اجراء العمليات الحسابية بطريقة موثوق
التي تدل على التنفيذ التلقائي لعمليات معيئة و توليد
التشغيل الذاتي يستطيع علماء الحاسوب ان يفهموا كيف تستطيع الآلة ان تحسب الدوال و تحل
المسائل والاهم من ذلك؛ ماذا يعني ان دالة تعرف بائها قابلة للحساب ع000(01001 او لسؤال
يوصف بانه قابل للحسم (او يمكن اتخاذ قرار فيه) 18د08650.
ان الآلات ذاتية التشغيل هي عبارة عن انموذجات رياضية مجردة لآلات لها القدرة على
انجاز عمليات احتسابية على مدخلات تتحرك من خلال سلسلة من الحالات. في كل حالة من
حالات الاحتساب وهناك دالة انتقل ‏ «001000 0081000 تقوم بتحديد الحالة المقبلة للآلة
016 تقوم الآلة بقبول المدخلات و تنهي عملها.
إن من اهداف نظرية التشغيل الذاتي ولقدصمانة !0 (:0ع<ل تطوير الاساليب التي
يستعملها علماء الحاسوب لوصف و تحليل السلوك الديناميكي للانظمة المتقطعة ع:م:
8ازة؛ التي فيها تأخذ عينات من الاشارات بشكل دوري عمتاصصدة لقصعزة . و
تحديد سلوك هذه الأنظمة من خلال الطريقة التي يجري بناؤها بها من ذاكرة ودوائر ار
م الادخال أنو10 'ض ان يكون بشكل سلسلة من الرموز تنتمي الى مجموعة منتهية
إذ أن « يمثل عدد المدخلات.
» الاخراج 08مه0: هو سلسلة من الرموز تنتمي الى مجموعة منتهية 7. وهي
المجموعة [70 .. . . ,3772 ,771) إذ أن « تمثل عدد المخرجات.
هناك اربعة انواع من آلات التشغيل الذاتي:

مقدمة في النظرية الاحتسابية
عمتطعمد غ710 .4
ان التاريخ الذائي فرج من لم الجاسوب بوضبحة
مجموعة واسعة من التطبيقات. وإن أول الناس إلذين تأملوا في مفهوم آلة الحالات المنتهية ‎٠‏ هو
فريق من علماء علم الاحياء 585نع131010 وعلماء النفس 0521001081815 وعلماء الرياضيات
701000111005 والمهندسين 60810888 وبعض علماء الحاسوب الأوائل الذين كان
يجمعهم اهتمام مشترك؛ وهو نمذجة عملية التفكير لدى الإنسان؛ سواء في المخ أو في جهاز
من علماء الفسيولوجيا العصبية؛ إذ كانا أول من قدم وصفا الحالات المنتهية في عام
07" _قدمت هذه الدراسة مساهمات كبيرة لدراسة نظرية الشبكة العصبية و نظرية
آلات الحالات المنتهية و نظرية الحساب وعلم التحكم الآلي 080081108إن. في وقت لاحق؛ قام
اثنان من علماء الحاسوب جورج ميلي (اةع11 .0.11 و اويلرمور ع:1100 .15.1 بتعميم
النظرية الى آلات ذات قدرات اكبر في بحوث منفصلة؛ نشرت في عامي 1955 و 1956.
1 : تمثل مجموعة الحالات المكونة للثلة وهي مجموعة منتهبة.
: تمثل مجموعة الابجدية.
عاب ا «ع1:ة5
أي أن تكون بالصيعة الثالية.
5 : تل حالة البداية عقا لمتلاصا ‎٠‏ إذ أن 16 6 5.
تمثل مجموعة حالات النهاية 518166 لقصاط. إذ أن 16 156

مقدمة في النظرية الاحتسا
تستعمل نظرية الآلات الذاتية التشغيل في علوم الحاسوب في امور كثيرة منها:
© تطوير برامج للتحقق من صحة وسلامة الدوائر الرقمية.
© محلل المفردات +0212 1.1001 لمعظم مترجمات لغات البرمجة :400/1011
أي المكوّن الذي يتم بتحليل النصنّ الدّاخل (البرنامج المصدري) 1108:1000 5010168
إلى وحدات منطقية (مفردات)؛ كأسماء المتغيرات؛ والأعداد والتتقيط.
© برامج لتحليل صفحات كثيرة من الإنترنت؛ والبحث عن كلمات معينة أو انموذجات
2 آلات الحالات المنتهية ‏ (15831) وعمتطاعم11 عنما عانماط
آلة الحالات_المنتهية 1751/4 هي عبارة عن انموذج ا لجهاز احتسابي بسيط
©0601 [1000ا018م00. تمتلك هذه الاجهزة حجما صغيرا جدا من الذاكرة و يعالج
مدخلاته بصورة مباشرة 00100©6. نعني بهذا أن الجهاز يقرأ رمزا واحدا خلال وحدة الزمن و
يقوم بمعالجته. و يمكن النظر الى آلة الحالات_ المنتهية 15518 على انها جهاز يتكون من
شريط يوضع فيه الخيط الرمزي ع0 كادخال للجهاز. ويبداً الجهاز من الحالة الاولى والتي
تسمى حالة البداية (0ن)؛ كما يوجد رأس للقراءة يبداً القراءة من شريط المدخلات من جهة
اليسار متحركا نحو اليمين وفي كل مرة يقرأ رمزا واحدا و عند انتهاء الرموز او عند
حصول خطأً. وفي كل مرة يقرا فيها رمزا يدقق في جدول الانتقل ع1طة1 ص«متاتفطة 71
أن 8 تمثل الرمز المدخل وان : تمثل الحالة الحالية و (ن تمثل الحالة التي سينتقل اليها
اعتمادا على الرمز المدخل م. الشكل ( 1-2 ) يوضح المخطط الذي يمثل آلة الحالات ال
نراها عادة في مداخل الفنادق والمطارات والمحلات التجارية
ها. يوجد متحكم :60000116 يقوم بالسيطرة على فتح الباب عند اقتراب جسم مسافة
. في هذه الأنواع من الأبواب تكون هناك منطقة أمام الباب في حالة وجود أي جسم

الشكل (1-2) مخطط كتلي لآلة الحالات المنتهية
تسمى (1004180) . في هذه المنطقة هناك مجسات تستشعر هذا الجسم ٌوتنفل الإشارة
إلى الفتحكم ©0011 الذي يقوم بتحليل وتفسير هذه الإشارة ثم يصدر أمرا إلى
لتقوم بفتح الباب فيكون الباب في حالة 0(60. كما أن هناك منطقة
خلف الباب تسمى (000 18608 إذا وجد عندها جسم يقوم المتحكم بإصدار إشارات تبقي
الباب مفتوحا بالقدر الكافي من الزمن لكي يعبر هذا الجسم من خلال الباب . وإذا كانت
حالة الباب 008 ووجود جسم خلف الباب فإن حالة الباب تبقى 0080 وذلك حتى لا
يتعرض هذا الجسم للأذى إذا جرى إغلاق الباب. أي أن مهمة المتحكم هي تغيير حالة
الباب من 010860 إلى 0080 والعكس.
هع لمم
الشكل(2-2) مخطط حالة متحكم الباب الالي
من الشكل (2-2) نلاحظ أن هناك حالتان للمتحكم هي 010880 و 0080 وكذلك أربع

مقدمة في النظرية الاحتسا
احتمالات للقيم التي يمكن إدخالها إلى هذا النظام .وبناءً على هذه المدخلات يقوم المتحكم بتغيير
»_ الاثنان 13007 وتعني أن هناك جسمان أحدهما أمام الباب والثاني خلف الباب.
»لا احد 1161006 وتعني أن لا جسم أمام الباب أو خلفه.
ويوضح المخطط في الشكل ( 3-2) أنه:
1. إذا كانت الحالة الابتدائية 1050© وجرى إدخال إشارة :1166018 او اشارة "روع18
فان الباب سيبقى في حالة 010860.
2. وإذا كانت الإشارة 3007 فلن يفتح الباب وتبقى الحالة 010880 حتى لا يتعرض
للأذى الشخص الموجود خلف الباب إذا جرى فتحه.
3. في حالة كانت الإشارة المدخلة 13004 فقط تتغير الحالة إلى 0080
4. أما إذا كانت الحالة الابتدائية 080 فإن استقبال الإشارات 800 و 2001 و ع1
سيبقي الباب في حالة 2(0ز0.
5. وفقط في حالة واحدة هي استقبال الإشارة:1181008 يتم الإغلاق.
بعطتعلا
الشكل(3-2) مخطط آلة الحالات المنتهية للباب الالي

مقدمة في النظرية الاحتسا
إن دراسة متحكم الباب الآلي كأنموذج لآلة الحالات المنتهية تعد مفيدة؛ لأنها تقدم طريقة
واضحة لتمثيل هذا النوع من النظم كما هو واضح في المثال السابق .فالمتحكم هو عبارة عن
حاسوب يمتلك ذاكرة بحجم ثنائية واحدة 1314 ع00 يمكنها تسجيل الحالة التي يكون عليها
المتحكم هل هي 010880 او «©(0. وهناك بعض الأجهزة التي تمتلك ذاكرة محدودة ولكنها
أكبر قليلا من هذه . فمثلا حالة متحكم المصعد الآلي 121600808 يمثلها رقم الطابق الذي يوجد
عليه المصعد في لحظة ما. أما المدخلات فيمكن أن تكون الإشارات التي يجري إرسالها
بالضغط على أزرار موجودة على لوحات للتحكم في العمليات المطلوبة من المصعد القيام بها .
وهذا النوع من المتحكمات يوجد في الكثير من الأجهزة المستعملة في البيوت متل الغسالات
وأجهزة التبريد والتكييف وكذلك توجد في الآلات الحاسبة والساعات الإلكترونية وغيرها.
ولوصف آلات الحالات المنتهية رياضيا فإنه يجب فعل ذلك بطريقة مجردة أي دون ربط ذلك
. آلات الحالات المنتهية غير المحددة عاتم عتامت 1100061
(ختاي «متتسمسم
2 آلات الحالات المنتهية المحددة
تمثل آلات الحالات المنتهية 151/1 آل مجردة لها وضع داخلي أو حالة في كل لحظة.
تستطيع هذه الآلة قراءة سلسلة من الرموز على التوالي باتجاه واحد (دون إمكانية العودة إلى
رمز جرت قراءته سابقاً) والانتقال إلى حالة أخرى حسب الرمز المدخل والحالة الداخلية
المحددة 801000318 10146 0616201101511 و يرمز لها بالرمز 8ع0 ؛ تعرف رياضيا
على انها نظام يتكون من الخماسي:
1 : تمثل مجموعة الحالات المكونة للآلة وهي مجموعة منتهية.