موسيقى
ماشي بسم الله الرحمن الرحيم و صلاة و سلام عشان
المواصلي اليوم ان شاء الله يا شباب بدنا نراجع
الامتحان نص الفصل اللي أخدناه يوم التلاتة الماضي
نمر على الأسئلة و نحلهم واحد واحد طبعا في عندنا
هنا في بداية في سؤال احنا استخمناه اللي هو الشق
التاني من السؤال الأول السؤال الأول زي ما انتوا
شايفين بيطلب بيعطيلك regular expressions و بيطلب
منك اللي هو إيش to describeالـ strings اللي
generated من هذا ال regular expressions دي بساطة
شريطة السؤال ال expression الأولاني
هو عبارة عن أنت لازم يعني لازم تذكر عدة مجموعة
نقاط أول إشي أنه ال string made of a's and b's صح
هم التلاتة كلهمA's and B's الـ strings مافيش أي
alphabet كاركتر آخر غير الـ A's والـ B's فهذه
النقطة بتود تذكرها النقطة التانية أيش بدك تذكر
بالنسبة لـ A هذا بدك تذكر أنه في ملاحظة أساسية و
هي أنه بيبدأ بالـ A و بينتهي بالـ A صح؟ و جوا إيش؟
عدد على غير محدود من ال .. إيش؟ من الكاركتر بس
الأخر صح؟ فإن هذا الوصف ماحن تلات نقاط أول شيء أنه
strings of a's and b's النقطة التالية أنه
unlimited الطول
تبعه يعني النقطة التالية أنهاش starts and ends
with a بكفيبكفى فى اشى تانى حد ممكن نضيفه كوصف لـ
strings المتولدة من هذا ال expression اللى بعده
هذا هذا برضه كذلك الحاجة ككل strings of a's and
b's limited لأ برضه مش unlimited okay بس مافى
حكاية اللى وان بيبدأ با وان بي هو متكون من ايش any
combination of a and b بظبط بمعنى انههل ال
combination او expressions يعتبر الموضوع هذه؟ ال
combination يعني تشكيلة .. تشكيلة .. لما بقول
expressions؟ هو .. هو هذا ال expression .. احنا
اللي ال expression بينتج .. مش بينتجش expressions
معمول أقصر عشان ينتج أو يولد strings و ال strings
هذه فيها combinations of characters characters
اللي لنا هنا نفس الشيء strings of a's and b's
unlimited lengthالان هل في صفة أخرى مميزة؟ يعني زي
ما أنه هداك بيبدأ بإيز و بيته بإيز، بيبدأ و بيته
بإيز، هل هدا في إيش مميز؟ لو لاحظت أنه أنتالجوس
اللي جوه ممكن يتكرر في الـ zero or more يعني حتى
ممكن مش موجود من أصله الجوس اللي برا يعني الجوس
اللي جوه في يدك ال B برضه كمان نجمة بمعنى انه ممكن
تكون موجودة او مش موجودة واللي جوه برضه ايسولون او
ايه يعني يعني كل الاحتمالات اللي فيه او كل ال ..
أنا من الاحتبالات أو كل ال characters وارد ان تبقى
موجودة او ماتبقى اش موجودة السؤال
التالت برضه بدك تقول strings of a's and b's برضه
unlimited لأن في عندى هنا star و star هذا ممكناش
يمدى الجزء اللى بعد ال star هذا معروف طوله عندى
حرف ال a حرف ال a هذا لازم يكون موجود بعد
هي كده خليط بس هي a or b بعد هي كده a or b معناه
ذلك ان انا في عندي على الأقل طول ال string تلت
characters صح؟تلات characters على الأقل والتي تالت
من ورا a مظبوط جامع اللي هي كان ممكن the zero or
any length of .. okay فانا ممكن انت تيجي تقول هنا
strings of a's and b's unlimited length بس تقول at
least three characters صح at least three
characters at least three characters على الأقل تلت
charactersال character القبل الأخر مش القبل الأخر
التالت من الأخر اللي هو ايه؟ ايه التلت من قبلك
تذكروا عنه؟ هنغنيه سؤال، إشي تاني، بدي أقوله،
أضيفه، تمام، هنروح على سؤال تاني، سؤال تاني شوية
بخبف بس على الفاضي، ليش؟
أولاً Indicate three plus label a,b هذا مش موجود
فبتجيب تقولي none exist ال .. بي .. بي .. give the
transition table ال transition table برضه بسيطه لل
NFA لسه جاب العملية التحويل و طبعا بتطلب تحويل بس
في ال C لسه ال NFA بيبقى محط اللي هم ال stays على
رؤس الأسطور و ال alphabet characters على رؤس
الأعمدة صح؟هي zero ايش ال states لانها zero و واحد
و اتنين و تلاتة مظبوط او الأرقام هذه نفسها ال
states اه واحد اتنين و تلاتة ايش ال alphabet
characters ال a و ال b فعندك الان من ال zero إلى
ال a من ال zero عبر ال a بيوديك على بس انا شوية
بدأ اوسع اني هذه لان محتاجين واسعة
بوديني على واحد من ال zero عبر ال a بوديني على
واحد و بس و ايضا بوديني على اتنين هذه طبعا ايش
بحطها في set السؤال انا مش هحط ال set عشان التوضيح
لان من واحد عبر ال a بوجعني على واحد و ايضا ايش بس
بالظبط
اتنين من اتنين عبر ال aمافيش مافيش صح؟ من اتنين
عبر ال B مافي اه تلاتة في عندك واحد من اتنين عبر
ال A عبر ال B عملناه من اتنين عبر ال A مافيشش
مافيشش صح عبر ال B فيه فيه يعني احنا ناخدها ال A
في الأول و بعدين يبقى مافيشش مافيشش طبعا التلاتة3
,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1
,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2
خلّينا نضعها لحظة جدّا
هنا في ال convert يمكن يلزم ويمكن لا يلزم مش الآن
بتبين معنا بس الان احنا نتفجر على ان هذا هو ال
transition table تبع ال NFA تبع ال NFA تبع ال NFA
تبع ال NFA تبع ال NFA تبع ال NFA تبع ال NFA تبع ال
NFA تبع ال NFA تبع ال NFA تبع ال NFA تبع ال NFA
تبع ال NFA تبع ال NFA تبع ال NFA تبع ال NFA تبع ال
NFA تبع ال NFA تبع ال NFA تبع ال NFA تبع ال NFA
تبع ال NFA تبع ال NFA تبع ال NFA تبع ال NFA تبع ال
NFA تبع ال NFAالـ E-closure تبعها الـ E-closure
لازم يكون في عيننا ابسلون transitions صح ابسلون
edges و لازم مافيش shape مافيش مشكلة لإيش لأن اول
ما بنبدأ نحط الاية ال E-closure نفسها E-closure
بالظبط بتبدأ تبع ال zero بتبدأ اصلا بال zero و
نسيله مفتوح احساس نظيف في ال epsilonنضيف اذا فيه
edges بالأبسلون نضيف نضيف ال states اللي بتودينا
عليها هذه ال edges مافيش شيء خلاص بسكر ال set هذا
ال set هذا نعطيله اسم label الأولى اللي هو ايش
نقول انه a لان انا بدي احسب من اللي هبني هدا بدي
احسب ال D trans ال a معكل واحد من ال alphabet
characters مع ال a مرة مع ال small b مرة ايش ال a
هذا هو ال set اللي يحتوي على ال state الواحدة اللي
هي zero طيب من ال zero عبر ال a ايه
اتوا طيب
ماشي مافيش اشي تاني لان نفس الشيء من ال
مافي شيء فخليني بس انا بتستخدم ال nouns for اي هذا
بدل الشحطة يعني ما اقنع الا انا خلاص هذا ال set
الان بتعطيله اسم بتعطيله label بيه الان بتحسب ال d
trans تبع من ال b مع ال a small و مع ال b small
يعني مين في ال b
الواحد عبر ال A واحد
و اتنين الاتنين عبر ال A واحد و اتنين الاتنين عبر
ال A واحد
و
اتنين
أيش يعطيني ولا شيء فخلاص بسكر ال set هل الآن جديد
عليك؟ لأ هو نفسه بيه بعطيه وش label جديد صح؟
هذا اللي هو ال بي واحد و تاني عمر ال بي واحد و تلت
ده؟ ده اشي صح واحد و تلت اه اه واحد و تلت صحالواحد
في والهدا واحدة تلاتة والاتنين يعطينا واحدة تلاتة
صح هذا بناسميه C هذا بناسميه ايش؟ C, C capital
الان بناحسب لل C دي Trans عبر
ال A وعبر ال B عبر ال A وين ال C؟ واحدة تلاتة هي
واحدة تلاتة1 عبر ال a قطعي 1 و 2 و عبر ال 3 عبر ال
1 و 2 1 و 2 هذا اللي هو نفسه D مظبوط؟ لأن هذا فش
فش خلاص ماضلش
لما نبطل يطلع معايا new sets سلسة جديدة انا صار
عندي ال DFA states هم ال A و ال B و ال C و
هذه ال D ترانز بيعطيني ال moves بتاعتهم بمعنى ايش؟
DFA state و .. هاي
ال A وهي ال B وهي ال C ال A عبر ال A فعطيني B
مظبوط ال A عبر ال B small فعطيني ولا إشي ال B عبر
ال A فعطيني C لأ هذا B هذا ال C تأشر هنا
الـ C عبر ال A سموه تعطيني ال B عبر ال B سموه
تعطيني ال Phi الان
بتدرسم ال DFA هاي
ال A وهي ال B وهي ال Cلأ من a عبر ال a بتديني على
b صح و
عبر ال .. okay ال b عبر ال b بتديني على b صح و عبر
ال .. لأ a .. a و عبر ال .. عبر ال b بتديني على ال
c ال c عبر ال a
تمام؟ إذا عملت هذا الكلام okay بس الصح من هذا
الكلام أنك أنت تعتبر الـ Phi علي إنها DFA state
هذا الكلام هيك بيكفيني بس لو أنت بدك الصح اللي هو
صح بتحط تعتبر ال Phi هي ده قبلها state بتعمل إليها
state بترسم رسمة تانية هنا فالـ Phi اعتبرناها إيسر
لا لا إبسلاتالإبسلون بيحطه رمز لما نحكي عن الهو
non-terminals انما في ال non-terminals وفي
المجموعات الإبسلون
لا يرمز إلى مجموعة الإبسلون يرمز إلى عنصر يعني
بيحطه كعنصر في المجموعة لما هو مجموعة بيستخدموهش
في الخاصية لو أنا الأن أتبر ال file على أنها state
رسمها هذه نفسها، بدي أضيف بسم الأزرق، رسمها هذه
نفسها بالأزرق، عادي، هذه الـPhi الآن،
بدي أضع الـPhi كـState هنا الـPhi عبر الـS، خلّيني
أقول الـA عبر الـB، و أخرج على الـPhi و
الـC عبر الـB
أقول ايش؟ اولا الـ B اولا الـ B مظبوط الان هذولتين
فاي و فاي يعني بقدر اعمل زي هيك A مع B A
او B بيرجعوني انا في فاي انا في ال empty set لو
اخدت A و انا في ال empty set لو جاني A او جاني B
برجع تاني على نفسيOkay فإما هذا ال background زي
ما هو يا إما بدون الأزرق بيقدر الرابط okay ننتقل
على السؤال اللي بعده السؤال اللي بعده حد
بيقدر يحلو
خلّينا نكبر الرسالة شوية اذا
انا
اعمل
case اذا
انا اعمل case
الأول اشي هو C بيساوي next car زي ما هو معمول في
ال net نفس ما هو معمول في zero بس بتغير أرقام ال
states بس بنتجي من ال case أه أه بس انت بدك تنكم
انتبه لإنه في قفصي أحيان المرحلة بعضكوا بتختلط علي
الأمر ال next car الان F C بيساوي احنا في ال واحد
فا إيش بتساوي state بتساوي اتنين else if c بتساوي
أكبر من then state بتساوي تلتة خلاص else state
بتساوي أربعةو بعدين بدي اعمل break عشان يرجع يكمل
يجرح a new character هذا case 1 case 6 نفس الشيء
بس هيبقى فيه لها ال F واحدة و ال S مافيش تلاتة
شروط
السؤال اللي بعده
ستعمل derivation صح؟ left most و بعدها right most
SS ضرب ثم تستبدل الأول واحدة الشمال باليهش بالهالي
والهالي والهالي الاسر الزائد الاسر الزائد ثم تنزل
التانية ثم الضرب تعوض ال إيه؟ تعوض ال إيه؟ الهالي
والهالي والهالي بالإيه؟ ثم تنزل الباقي كما هو تعوض
التانية
بعد ما عوّدت فلس
هذا ال M لما بتعملها هذا كله ال M left most لما
بتعملها right most
اساس بره بره بره بره بره بره
لأ هذا السؤال .. انا مش في left factoring .. فش في
right factor .. left factor مفيش .. فش .. فش .. فش
.. فش .. فش .. فش .. فش .. فش .. فش .. فش .. فش ..
فش .. فش .. فش .. فش .. فش .. فش .. فش .. فش .. فش
..
والله يا شيخ انا هذا مادة انا انظر فيها بس احنا
يعني السؤال هذا مافيش فيه left factoring و حلو
left recursion احنا فيه انا سؤال تاني لل recursion
عشان هيك مقدرش هذا اخد منك حلو على ال recursion لأ
انت بس اعمل هداك اعمل هداك بتاني
الان هذا السؤال هذا اللي بده recursion وهذا فيه
direct وفيه indirect تمام؟ وهذا بده تركيز هذا
الجبل الأخير صح؟ الان انت عشان ت .. عشان ت .. قدام
.. قدام يصير فيه direct قدام يصير فيه direct ترينا
تطلع كيف .. بده ..بعدين اجيب الحل هنا كله بس ايش
بده اساوي في الأول احنا طبعا ال algorithm لازم
نرتب ال symbols بترتيب .. فبده نيجي نقول A وB وC
ولا اكتب بالأسود أحسن
لأن هذول التفتيت بدي اجي تحت كل واحد من ال symbols
اكتب ال rules تبعونا يعني a في عندي ال rule هدى بي
كابتل اكس واي وفي ال rule التاني دي a x صح
انفصلتهم هين two rules اه ففصلتهم في سطرين ال b
إلى ال rule واحد اللي اكسي كابتل دي
الـ C can have the form of A والـ C can have the
form of C صح؟
الـ D can have the form of D صح؟ الـ D can have
the form of D صح؟ الـ D can have the form of D صح؟
الـ D can have the form of D صح؟ الـ D can have
the form of D صح؟ الـ D can have the form of D صح؟
الـ D can have the form of D صح؟ الـ D can have
the form of D صحهذا ونطلع على اللي جابله و بعدين
هذا و اللي جابله و بعدين هذا و نطلع على اللي جابله
صح؟ كل واحد و أنا مابتجل عليهم بدي اعتيب لهم I و
اللي جابلهم J يعني انا بقى براقف هنا هذا I و هذا J
و براقف هنا هذا J1 و هذا J2 صح؟ فانا بدي ا .. ا ..
ا .. أسوي كلام هذا على شكل .. على شكل التالي اللي
هو هاجي اقول ان عندي Iعندما تبحث عن I تجد I ناقص
واحد جي تتبع من I ناقص واحد ل I
ناقص واحد ل I ناقص واحد ل I ناقص واحد ل I ناقص
واحد ل I ناقص واحد ل I ناقص واحد ل I ناقص واحد ل I
ناقص واحد ل I ناقص واحد ل I ناقص واحد ل I ناقص
واحد ل I ناقص واحد ل I ناقص واحد ل I ناقص واحد ل I
ناقص واحد ل I ناقص واحد ل I ناقص
واحدI2 I2 بمشي J1 وخلص I3
بمشي J1 و J2 صح I4 بمشي 1 و 2 و 3 okay لأن لما
تبقى I1 AIهي بقى عن ال a و a j مافيش شي مظبوط لما
تبقى i أربعة ايش ال a i بتبقى ال d مظبوط و ال a j
واحد تبقى ال a مظبوط هنا ال d b و هنا ال d cهنا
يبقى بالتالي بي اي و سي
اي و سي بي و سي اي و سي بي اي
و سي بي و سي بي و سي بي و سي بي و سي بي و سي بي و
سي بي و سي بي و سي بي و سي بي و سي بي و سي بي و سي
بي و سي بي و سي بي و سي بي و سي بي و سي بي و سي
بمعاها some grammar هل في أني rule رأسها B و body
تبعها بيبدأ بA؟ لأ مافيش هذا طبعا مافيش هل في أني
rule رأسها B بيبدأ بA؟
نعم
هي الـ C كانت في الـ Form A هذي الآن إيش بيسويها؟
إيش بيسويها؟ بدي أعملها replacement بدي أشطفها و
أحط بدالها replacement تبعها إيش ال replacement
تبعها؟ أولا لازم يكون في عندي هذي إيش قولنا
الجامعة مافيش شيء الجامعة أتبع إبسلون صح؟ بعدين
بدي أطلع على ال sigma's sigma one و sigma two و
sigma three إيش ال sigma هذولة؟ ال A نفسها إيش ال
productions تبعونها كل production ال body تبعها هو
سيجما و لا لأ صح سيجما تلاتة مافيش شيء ال
replacement هي انه بيقوللي شيل هذا ال rule و حب
بدالها مجموعة من ال rules see can have the form
ايش ايش بنجيبالـ Gamma مطبوعة
بياش بالـ Sigmas صح؟ نرجع تاني على ال algorithm
will replace each production of the form AI AJ
Gamma ب .. بحط ال Sigmas في الأول مطبوعين بالـ
Gamma يعني هاي ال Sigmas بيكس
بعدها gamma بعدها كمان C تانية X بعدها gamma
الجامعة مافيش صح فولا حاجة الجامعة أنا بتشطبها دي
و بحط بدالها دول التانية مظبوط صح فهي بتنشطب و
بييجي بدالها
ماذا قلنا الجامعة كانت هنا ولا شيء و ال sigma هي
sigma واحد و sigma اتنين مافي اشي غير دلوقتي هاي
بي اكس واي و هاي اش اكس لان ال replacement شيلنا
هذه و نحط بدل ايشمين هذول اللي بتلقى C Bxy مع C X
خلاص
ال literature نروح لل literature اللي بعيد ولا في
إيش ضايق في ال algorithm في إيش اللي هو eliminator
immediate هل في immediate مع اللي نتجه من إجداد
هذول هل شفناها خلاص هذا طبعامافيش نيجي هنا الان
عندي ال C و B هل في يدي ال C head left hand side و
B في بداية ال body هاي الجديد هالي صح معاهي
شبابكو ال C
BXY كمان؟ وين الجامعة هنا؟
الجامعة
هي ما بعد الـ B طب
ال sigma's ده شوف ال B ال productions تبعهم منها
فشلا يالي، فهي ال sigma الوحيدة للي صح؟ صح؟
اللي هي ايش C capital D capital لان بدى اشيل هذه
ال rule و اضغط بدلها ايش
ممكن تأتي في الأول الجامعة ال
sigma في الأول و بعدين مطموعة بالجامعة مش فقط
sigma واحدة صح بيكس
واي مطموعة بال cd هذا ال rule الجديد
العكس من الـ Sigmas اه انا بتطلع هنا تمام فاحنا
كنا فاحنا بنقول ايش وين الجامعة هنا الجامعة هي ال
XY اللي هي الشق اللي بعد ال B و ال Sigma اللي هي
ال body تبع ال production تبع ال B اللي هي ال CD
CD لان بنا نستبدل هذه ال productionبنضع C ثم S ثم
Gamma فهذا يبدأ تهترق ويأتي بدانها ال roll هذا قبل
أن نعود إلى ال iteration اللي بعد نشوف هل صار في
عندي النتج اي left اي immediate left recursion نعم
في عندي هنا immediate left recursion فابد أشيلهكيف
أشيلهم؟ لازم أطلع على كل ال production سبعة الـC
هدى و هدى و هدى مظبوط؟ الـC
كان هو الـform C small الـC كان هو الـform X small
و الـC كان هو الـform CDXY اللي هو هدوه اللي هيش
بنعتبرهم احنا Beta 1 و Beta 2 اه
وهذا ايش نعتبره Alpha تمام كيف بشيل ال left
recursion ال immediate بقول C كنارة فورم C small
وحط C كرة بقى C prime C كنارة فورم X ال Beta's
بحطهم و بحط بعدهم مين بعدين
بجيب ال Alpha
أسف فيها D هذه صح؟
صحيح؟
هذي ال immediate هذي ال immediate المفروض في هذه
ال productions بعض منهم سريمة
اللي فيها مشكلة .. اللي مافيش فيها مشكلة بعتبر ال
bodies بتبعتهم بيتاس بيتا واحد و بيتا اتنين و
الاخر اللي فيها المشكلة بعتبر شق ليه بعد ال symbol
هو ال alpha okay لإن عشان أصلح بروح بجيب ال symbol
الأساسي اللي هو ال C بحط ال betas كل واحد منهم
وراها إيش ال C prime بعدين بجيب ال alpha بعدين
الـ C' مظبوط
بعدين بعمل واحد تاني الـ C' بالإيش بالإبسن بمجرد
ان انا اشيل هذه و احط بدالها هدولة لأ بدي اشيل كل
هدولة و احط بدالهم الاربعة هدولة مظبوط بدي اشيل كل
ال production سبعة ال C و احط بدالهم ال
productions الجديدة خلهم هنا بس انت تخيلهمالان
شغلنا هذا الكلام لانه لم يبقى فيه نفط الكتر مظبوط
انتجلنا هنا الان دي ايه هل في عندي production ال
head تبعها دي و ال body تبعها بيبدأ ب ايه مافيش
هاي كل production سبعة ال D ولا واحد منهم ينطبق
عليه لان في كل هذه الحالات مابنسويش ولا حاجة لان
كل الشغل تبعنا حصل في production سبعة ال C عملنا
معالجة ل ال Cكان هذا form A لهذه ال production
ومعالج لهذه ال production هذه ال production
بدلناها بهذه التنتين واحدة منها هي اللي دخلتنا على
المعالج هذه فبدلناها بهذه لأن بعد ما طلعت هذه
اكتشفنا ال immediate left recursion فعلجناه فصار
في هذه ثلاث معالجات لهذه وهذه ولل left recursion
ال immediate
سؤال الأخير بسيط
جدا الفرصة
تبع هذه المجموعة هو الفرصة تبع A لحاله إلا إذا كان
الفرصة تبع A يحتوى على أبسلوتر إيش الفرصة تبع A؟
وين ال A؟ هاي ال production تبعها إيش الفرصة تبع
A؟ ال D وال A بال Cبالتالي هذا الكلام ال
D والA والC هل أسكر ولا لأ إذا إبسلون واحد من
هدولة بسكرش بروح أجيب ب .. بروح أجيب الفائز تبع ال
D بس لأنه مش موجود بسكر صح ولا لأ؟ لأ هذا الفائز
تبع هذه المجموعة
وهنا C هنا برضه نفس الكلام اللي حكيناه هنا A D A C
هجيب ال first تبع S و ال first تبع A انما لو كان
عندي epsilon هنا لو كان في عندي هنا epsilon هذا
هيدخلني على ايش بعد ما اجيب ال first تبع A هخليني
اجيب ال first تبع ال symbol اللي ورا فهي كل الاسم
في حد عنده سؤال تانييعطيكم العاشر