بسم الله الرحمن الرحيم والصلاة والسلام عليكم ورحمة
الله وبركاته اليوم إن شاء الله بنكمل .. بنكمل في
chapter ثلاثة اللي هو ال lexical analysis في
آخر محاضرة دخلنا في ال finite automata وشوفنا ال
transition diagrams كيف احنا ممكن نمثلها أو كيف
نمثلها على شكل the finite automata الـ Finite Automata
احنا عرفنا أنه فيها نوعين فيه Non-Deterministic
Finite Automata وفيه Deterministic Finite Automata
وقلنا إنه هذه الـ Finite Automata اللي هي State
Transition Diagrams في واقع الأمر هي خطواتنا
التمهيدية لبعد هيكم نعمل اللي هو ال analyzer ال
code تبع ال analyzer
وضعنا اللي هو ثلاثة ستة finite automata وكذلك
الحال برضه كمان عاوزين نشوف التحويل كيف يتم من ال
regular expression لل the automata لأن خطوة the finite
automata اللي هي تمهيد لل lexical .. ل generating
ال lexical analyzer هي نفسها مبنية على .. هي نفسها
مبنية على regular expression طيب فخلينا أولا نتأكد
وين احنا بالظبط و ضفنا في المحاضرة الماضية
طبعا شوفنا الأمثلة هذه كلها أنا ما أعتقد اللي هي
Finite Automata طبيعة الـ..
ثلاثة سبعة بدأنا في ثلاثة ستة .. ثلاثة ستة كله
except طبعا شوفنا ال example هذا هذا ال example أول
الشيء كان الهدف منه توضيح كيف أنه ممكن ال non
deterministic finite automaton ممكن
ال string الواحد زي هذا ممكن يتم تعرف عليه نعمل
accepting له ال non deterministic finite automaton
تعمل accepting له بأكثر من مسار واحد وهذا غير
مرغوب عشان هيك احنا الهدف طبعا ال deterministic
finite automata تمام؟
وقفنا هنا المحاضرة الماضية؟ أو بدأنا فيها؟ أو
قشينا فيها؟ طيب نبدأ من هنا ال deterministic
finite automata الهدف هنا في المحاضرة هي أن نشوف
ال deterministic finite automata بس
سأغير المسار لأنه بعد ما أتعرف على ال
deterministic finite automata والفرق ما بينها و
ما بين ال non deterministic اللي هي مثلها بسيطة جدا
بعد ذلك في ثلاثة سبعة بتحول للحكي عن التحويل
من regular expressions ل automatic هذا ال section
ثلاثة
سبعة واحد جاي عنوان ال conversion from NFA to DFA
الكلام
هذا كله جيد ولكن أنا تمام بدي آخذ الخطوة اللي جابله
اللي هي جابله أنا ما أعمل convert من NFA to DFA
بنزلني بالأصل كمان أني construct بنزلني لسه قبل
هذه الخطوة construct the NFA from من ايش من ال
regular expression بنزلني أشوف كيف how we
construct the NFA من ال regular expression عشان
بعدين أشوف كيف أحول ال NFA إلى DFA في الثلاثة
السابعة هروح أقفز على طول على ثلاثة سبعة أربع وبعدين
أرجع على ثلاثة سبعة واحد أنا
هآخذ هذه في الأول اللي هي ثلاثة سبعة أربع وبعدين
أرجع على هذه اللي هي ثلاثة سبعة واحد ثلاثة سبعة
واحد اثنين ثلاثة تمام بس احنا لسه بدنا نرجع الآن
قبل سبعة كله قبل section ثلاثة سبعة كله بدنا نرجع
على الـ.. اللي
هو ال deterministic finite automata ونجمل الحكي
الفرق ما بينهم وبين ال NFA ف deterministic finite
automaton اه automaton طبعا المفرد و automata اللي
هي الجملة is a special case صح هذا الكلام special
case of NFA there are no moves on input epsilon
epsilon اللي هو يعني ما فيش .. ما فيش input وبرضه
for each state S and input symbol A there is
exactly one edge احنا قلنا بالأصل أول ما حكينا عن
الفرق بين NFA و DFA قلنا أنه لما نكون في هذا ال
state ال edges اللي طالعة منها على other states
تمام ال NFA بيسمح أنه نفس ال input symbol ممكن
يكون موجود على أكثر من edge مرة في هذا الـ edge
ممكن أنجلني على هذا الـ state في هذا الـ edge
أنقلي على state أخرى أنا في one ممكن a تانجلني
على اثنين أو تانجلني على ثلاثة هذا NFA ماشي إنما
DFA لأ for each state S and input symbol A there
is exactly one edge بس واحدة اللي تطلع من هذه ال S
على other states وهذا كلام قلنا عمليا أنه إذا كان
ال NFA أنا بقدر أعبر عنها على شكل جدول والجدول
transition table والجدول بيسمح بيبقى فيه ending
من أحد ال states على input اتقال إلى two or more
states هذا في ال NFA ممكن لكن في ال DFA لأ ففي ال
DFA لا يمكن أشوف هذا الكلام أصلا الحواس هذه
ما بشوفهاش لأن الحواس هذه بتعبر عن مجموعة وأنا عندي
في ال DFA ما فيش مجموعة ما فيش إلا single state
single edge طلعناها single state تمام فهذا الكلام
الآن صار واضح لنا أنه أولا ما فيش فرق أساسي ما فيش
moves on input epsilon ثانيا أنه for each state S
عند input symbol A there is exactly one edge out
of S
هذه الكلام بيكرر اللي أنتو قولتوا حكاية ال sets و
curly braces أنها بتظهرش في ال table okay؟ الآن
احنا في الـ .. في الـ .. في الـ .. ال NFA و ال DFA
قلنا هم عبارة عن خطوات أو بيعبر عن الخطوات اللي
بتتم في التعرف على string أن هو مطابق ولا غير
مطابق لل pattern يعني أنا بتخيل DFA أو NFA لل
relational operator ال pattern تبع ال relational
operators كده ال identifiers ال أي واحد من ال
constructs تبع ال language كل واحد منهم لها
initial لها ال DFA أو ال NFA هذا ال DFA بيعبر عن
خطوات التعرف على ال input string هل هو مطابق لل
pattern تبعته ولا غير مطابق صح؟ يبقى هو عبارة عن
.. عشان يمكن نقول .. هو عبارة عن إما بيعطيني yes
أو no أن هذا ال string مطابق أو غير مطابق للـ.. لل
pattern تبعت الـ.. اللي أنا فيها لو أديها فيها
فاحنا ممكن نتخيل ال pattern بس في algorithm ال
algorithm هذه بتنفذ
NFA معين أو DFA معين بتنفذه بمعنى ايش بناء على ال
states اللي فيه وبناء على ال edges اللي طالعة من ال
states إلى ال other states بتقدر ال algorithm هذه
بتقول لي إذا كان ال input الفلاني a مطابق لل
pattern تبعتها ولا لأ إن لو احنا أعطينا للخوارزمية
دي an input string x terminated by end of line
character وعطيناها DFA دي طبعا احنا هنا بنقول NFA
أو DFA بس هو لازم يكون DFA وإلا بيمكن أن نرجع في
ambiguity فـ.. وعطيناها main start state ال zero
ومن ال accepting states من ال states اللي إذا
وصلنا إليها إذا وصلت إليها ال algorithm معناته ال
input اللي دخل is compatible with ال pattern تبعت
هذا ال DFA طبعا ال transition function هي اللي
بترجم ال DFA هذا هي اللي بتقول إن والله إذا كان إذا
كان ال input على ال character فلاني إذا كان ال
input على ال character فلاني إذا
كان ال input على
ال character فلاني إذا كان ال input على ال
character فلاني إذا كان ال input على ال character
فلاني إذا كان ال input على ال character فلاني إذا
character فلاني إذا كان ال input على ال character
input على ال character فلاني إذا كان ال input على
DFA DFA DFA DFA DFA DFA DFA DFA DFA DFA DFA DFA
الـ Algorithm تتكون من Loop أساسيا أول شيء جابني
ال Loop ال S اللي current state بتؤشر على S0 بالـ
C اللي هو next character نجرى ال character ومن
هنا ندخل في Loop A بحيث أنه كل مرة نجرى character
جديد لحد يتم إنهاء ال end of file لأن ال end of
file هو نهاية ال string x ففي كل مرة بنستدعي في كل
مرة دورة أو دورات اللي قعدت نستدعي ال move
function نقول هنا دلوقت في ال state كده وأمامنا
ال character وكده وأين نروح فهي بتعطيني ال new
بتظهر اللوك تمشي تمشي لحد ما في الآخر
بيخلص ال input لما بيخلص ال input هنطلع من اللوك
والآن إذا طلعنا و ال current state كانت واحدة من
ال final states يبقى ال input هذا مطابق لل pattern
تبع ال DFA وإلا بيكون not valid فإذا كان S is in F
فهنا capital بمعنى مجموعة states ف return yes وإلا
return هذه الفكرة الأساسية لل algorithm وبالتالي
بقدر أتخيل أن ال algorithm هذي عبارة عن algorithm
general algorithm بنعطيها أي definition أي DFA
انبنى على أساس ال regular expression
وهي بتقول .. و بنعطيها and string وهي بتقول اللي
كان ال string هذا مضبوط أو هذا مضبوط احنا الآن بعد
.. ها هي ال example هذا ال example هذا أولًا
اللي قدامنا هذا أكبر عن NFA و لا DFA DFA لو لاحظتي
مافيش ولا واحدة من ال states عليها H عليها epsilon
هذا أولًا ثانيًا مافيش شيء احنا باستخدام ال edges
اللي طالعين منها نكرر نفس ال label صح؟ okay فهذا
الآن هذا ال DFA يعبر عن هذا ال expression لو أنا
الآن أعطيته هذا ال input هذا ال input وباستخدمت لو
أعطيت لل algorithm هذا ال input وهذا ال DFA
الألغوريثم سيعطي yes لهذا ال input لأنه مطابق لل
.. مطابق لل .. مطابق
مطابق لل .. مطابق لل .. مطابق لل .. مطابق لل ..
مطابق لل .. مطابق لل .. مطابق لل .. طيب، الآن في
ثلاثة سبعة الكلام يتحول .. ينتقل إلى عملية التحول
من regular expression أو توليد ال automata اللي هو
ال DFA من بناء على ال regular expression في الأول
لازم نشوف كيف بنولد NFA من ال regular expression
بعد هيك بنشوف كيف بنحول هذا ال NFA إلى DFA عشان
هيك أنا ببدأ أنتقل زي ما قلت في الأول إلى 374 في
واقع الأول 374 بيطلب كمان رجوع لمراجعة الكلام
اللي حكينا عن ال regular expressions في الأول تمام
فهي 374 بيحكي عن constructing an NFA from a
regular expression بدي أرجع .. معلش استحملوني لأ في
البداية اللي حكيت عن ال regular expressions من
قصده بس مراجعة سريعة وبعدين هنا في section regular
expressions احنا حكينا عن ال regular expression
وعارفينه بس في شوية ايش rules بنبني منها إنه احنا
بنقول إن ال regular expression هو في واقع الأمر
بتكون من sub regular expressions يعني ال regular
expressions are built recursively out of smaller
regular expressions طبعًا فالآن
لو احنا رمزنا ل regular expression برمز R وبيجينا
بيقولنا ك L of R ايش نقصد
بنقصد ال language اللي مشكلة أو generated from هذا
ال expression وال language هي عبارة عن ايش ال set
of strings
مظبوط okay هو فعلاً ال regular expression بيعبر عن
نمط لكل هذا ال strings مجموعة ال strings المتولدة
من هذا ال regular expression بتشكل ال language
بتشكل language صح؟ ف L of R each regular expression
of R denotes يمثل أو يشير إلى a language L of R
which is also defined recursively هذه ال language
is defined recursively from the languages denoted
by a substring of R يعني إذا كان R هو مشكلة من sub
regular expressions كل واحد من sub expressions
هدول هو يشكل language تمام لأن R كله ال language
تبعته هي إجمالي ال languages تبعت ال sub
expressions بشكل أساسي أنا لو عندي طبعًا ال regular
expression جاء على أساس alphabet اللي بيبقى فيه
عندي alphabet هي اللي بتشكل منها ف أنا عندي لو عندي
character أنا بحاجة لدفن اتنين وأرجع لواحد Symbol
A هذه ألفابت والألفابت هذه هي عبارة عن مجموعة من
ال symbols A,B وربما Z كمان الآن كل واحد من ال ..
من ال characters أو ال symbols يسمونه الالفابت هذه
اعتبرها string صح؟ الآن هو في حد ذاته هذه ال
string أنا ممكن أتخيل expression خاص به هو لحاله
يعني زي هذا ال character A is a string فهو في حالته
مجموعة مجموعة تتكون من عنصر واحد مجموعة من ال
strings تتكون من ال strings واحد تمام فهذه
المجموعة من ال strings أتخيل regular expression
لها وأسميه a بس بتستخدم a كمتغيرة مثل ما هو عامل
هنا آسف a bold a bold هذا هو اسم ل regular
expression يمثل character واحد تمام فالآن بما أن a
bold هذا a bold هو عبارة عن regular expression
regular expression يرمز إلى string واحد ال string
واحد هو عبارة عن character فقط طيب ف ال l of a هي
عبارة عن هذا ال character الواحد وهذا أبسط regular
expression على وجه الأرض atomic regular expressions
كل ال regular expressions تتركب من بعضها فمنها من
مثل هذه ال regular expressions تتكون من regular
expressions الكبيرة الأبسط من هذا كمان اللي هو ال
epsilon ال set اللي يحتوي على الأشياء صح؟ وهذا ال
set بيقبل عندنا بال language of epsilon Language of
epsilon هي ال set الفاضي ال language of a هي ال
set اللي تحتوي على الأنصار وواحدة مبارة كاركتر من
كاركتر سباط الألفابت ممكن أنا أفكر برضه ب L of B و
L of C وكده تمام؟ هذا اسمه basis لبناء ال regular
expressions بصفة عامة الآن من هذا الأساس بقدر أفكر
بايش بإي ال operations اللي ممكن تعمل علي ال
regular expressions اللي بتمكنني أن أبني regular
expressions أكبر صح فبغض النظر الآن عن خد عندي R و S
وبغض النظر هم atomic ال R و S اتوميك صغير صغير ولا
هم composite يعني مركبين من ..
الـ bar هذا ال or هو .. يعني لو قدي أنا .. لو قدي
أنا suppose r and s are regular expressions
denoting كل واحد له ال language تبعته بجموعة ال
strings المتولدة منه respectively فهذا
هو regular expression مشكل من ال or تبع الاتنين is
a regular expression denoting ال language تبع ال R
union ال language تبع S صح فهذا عبارة عن regular
expression بتكون من R لحاله و S لحاله R لحاله له
language و S لحاله language وبالتالي ال regular
expression اللي الكبير it denotes a language هو
لحاله وهذه ال language هي ال union تبع ال language
تبع R وال language تبع S الآن هذا is a regular
expression denoting ال concatenation صح كل string
في ال language تبع ال R ملحوم ب string آخر من ال
language تبع S ال closure اللي هي إقرار إن أنا
بأمسك string من R نفسه مع أي string آخر من R نفسه
بكمية معينة فهذه عبارة عن ايش عبارة
عن operations احنا بنعملها على regular expressions
طيب عشان نبني regular expressions دي طيب يبقى أنا
برضه بقدر أعمل عكس يوم أنا بشوف regular
expressions كبير وبقدر أحلله إلى ال sub regular
expressions تحليل هذا بفيدني في عملية تحميل ال
regular expressions ل NFA لأنه أنا بقدر أبني ال
NFA الكبير تبع ال regular expressions الكبير من ال
NFAs الصغيرة تبعت ال regular expressions الصغيرة
okay تمام
بالـ example بيوضح كيف أنه لو أندي أنا ال alphabet
تحتوي بس على ال a وال b okay كيف هيده a or b
عبارة عن ال ايش هذا لحاله عبارة عن regular
expression يمثل ال a أو ال language تبعتهم هي
عبارة عن ال 6 في a وال L of B بي طبعًا capital بي
bold في ال N هذه اللغة وهذه اللغة عندما جلبت
الاسمبول regular expression a وregular expression
b وحطيت regular و regular وregular و regular و
regular و regular و regular و regular و regular و
اللغة الناتجة مش هتتغير لو أنا عندي r or r bar s
ولا s bar r نفس اللغة وبالتالي هذي الاتنين
equivalent two expressions are equivalent only إذا
اللغة المتولدة منهم متطابقة فهذه
ال expression بيعطيني لغة نفسها
equivalent يبقى commutative بقدر أعمل كمان
associative بمعنى أن بقدر أحط دولة في جوس أو أحط
دولة في جوس ويطلع برضه عندي نفس ال language فهذا
اللي يساوي هذا اللي يساوي اللي هنا معناته إيش اللي
على اليمين ال expression اللي على اليمين بيطلع نفس
ال language اللي بيطلعنيها ال expression على الشمال
ماشي هذه المراجعة ربما كانت ضرورية أو جزء منها
ضرورية على سبب أن احنا نقدر نبدأ نحكي الآن ونرجع
ثاني على عملية التحويل عملية التحويل الآن تحويل إيش
regular expression إلى ال NFA أيوة اللي هو أربعة
سبعة تلاتة سبعة أربعة okay هيتوا تمام from
constructed NFA from regular expression أنا الآن
بقدر آجي وأقول أن في عندي
الحالات الأساسية البسيطة جدا مبسطة لما نبدأ فيها
عندي أنا ابسلون ابسلون هو regular expression ال
language إيه ال language اللي هي عبارة عن أنا لأن
مش معنى بال language أنا معنى بشكل regular
expression هذا كيف أعبر عنه ب NFA في حياته بعمل
two states I و F F يعني final و I initial بأعتبر
الـ final الـ final وبضع page عليها بسهولة هذا و
طبعا هذا بتبدأ ب start يعني لازم أي NFA أو DFA
لازم يبقى له start هذا إيش دلالته لا يعني شيء الآن
هو لحاجة صغيرة لكن لما يجي من ضمن regular
expression كبيرة أو NFA تبقى regular expression
كبيرة يبقى له دلالة تمام فهذا ال basis الأولى زي ما
رأينا basis لللغة للتطبيق الاجتماعي الاجتماعي
الاجتماعي الاجتماعي الاجتماعي الاجتماعي الاجتماعي
الاجتماعي الاجتماع
حلو؟ تمام الآن ال induction أو البناء على ذلك أن
لو كان في عندي أنا two expressions two regular
expressions S و T وأنا عندي الشكل تبعه عندي ال NFA
هذا ال NFA تبع S وهذا ال NFA تبع T بغض النظر
لجوا بقدر أرسم ال NFA تبع S T
S
bar T على شكل أن ب .. طبعا كل واحد من دول ال two
NFAs ال NFA تبع S وال NFA تبع T له initial وله
final هذا ال initial وهذا ال final وهذا ال
initial وهذا ال final
باستخدام state جديدة لل figure كله نفسي S نفسي T
نفسي S نفسي T نفسي T نفسي T نفسي T نفسي T نفسي T
نفسي T نفسي T نفسي T نفسي
T نفسي T نفسي T نفسي T نفسي T نفسي T نفسي T
نفسي T نفسي T نفسي T نفسي T نفسي T نفسي T
نفسي T نفسي T نفسي T نفسي T نفس
الاتنين بيشاروا عليها هذه الآن أصبحت مش final و
هذه مش final وهذه مش start مش start تصبح هذا ال
start وهذا ال final واضح؟ حلو .. حلو ولكن NFA مش
DFA مش هو المطلوب أن هي بس خطوة لقدام اه بعد هيك
اللي هو إيش ال .. ال concatenation لما يبقى في
عندي expression هذا إيش بتاع هذا ال union اهلو كان
عندي ST sub expression .. regular expression و
regular expression يعني أنا لو عندي regular
expression بقول زي هيك مش مرة قليل ما حد شايفه هيك
الآن هذا regular expression يتكون من two regular
expressions هذوله بقدر أنا أسويه بالكافي اللي هيك
هذا ال regular expression يتكون من ال
concatenation تبع حالي مع حالي اللي هو بعد هيك بدي
أعمل ال concatenation لو عندي concatenation كيف
أسوي ببساطة شديدة بأخد ال NFA تبع هذا وال NFA تبع
هذا وبلحبهم عند ال final تبع هذه مع ال initial
تبع الثاني وبتصبح ال initial تبع الأولى هي ال
initial تبع كله وال final تبع الثاني هي ال final
تبع كله واضح؟ هنا لو أنا في عندي closure ال
closure اللي هي ال star
S*) هل هنا فيه طبع S S لحالة إذا كان هنا Star على
S معناته بدي أجيب قرار initial جديدة و final جديدة
أشاره من ال initial على ال final direct بالإبسلون
ومن ال initial جديدة على ال initial بالإبسلون
ومن ال final على ال final بالإبسلون وأرجي من ال
final على ال initial بالإبسلون تمام
Okay خلّيني آخد مثال شوية يتطبق هذا الكلام على
regular expression طويل اللي هو .. أنا regular
expression .. اللي هو هذا اللي اتواصلته okay ..
اللي كتبته هذا regular expression لو بدي أحلله إلى
sub regular expressions بيطلع معايا على شكل ال tree
هذه صح؟ معنى أن .. كله على بعضه هو الشيء مبني من
الـ a لحالها ال a لحالها هي عبارة عن regular
expression تحت ذاتها مش هحط سهم بس بدي أقول
أرواهاته هو regular expression يمثل ال a لحالها
بعدين ال b لحالها دول جوس لسه اه هذه regular
expression تانية ال M في اني regular expression
تلاتة هو عبارة عن الاش الاش ال .. ال .. ال .. ال
.. ال .. ال .. ال .. ال .. ال .. ال .. ال .. ال ..
الunion تبقى الاتنين هذه الأوراة صح؟ اه بعدين
هال R تلاتة مع ال closure تبعه R أربعة صح؟ مع ال
closure تبعه لأ مع ال ghost طبعا وجود ال ghost
equivalent يعني R أربعة وR تلاتة equivalent ما فرجش
ال .. الآن مع ال closure ب R خمسة ال closure مع ال
A R ستة ال closure بال A مع ال B R سبعة هو ال A
لحاله R ستة مع ال A R سبعة صح؟ الآن لو أنا جيك بدي
بس هذا ال regular expression R واحد أرسم ال N فيه
تبعته هو M هو مين؟ هذا و B هي ال NFA تبعها لأن هذول
الاتنين مع بعض بدي أبني منهم NFA يعبر عن ارتراتها
هذا الآن هي ك NFA لحاله وهذا NFA لحاله وبجيبهم
الاتنين بعمل initial جديدة و final جديدة صح بأخلي
هذا شير هنا بيأشر بإبسلون و شير إلى هذي بـ epsilon و
هذوله برضه بـ epsilon اللي هو بيطلع معايا هم صح
ولا؟ طبعا هنا هو عمل ترقيم سريع لأن هذا يقبل عن R
تلاتة مظبوط؟ طيب على R أربعة نفس الأشياء لأن R
أربعة ما أنجم بال closure تقدر تعملوا هيك وتجيب I
جديدة
بإيبسلون وهنا بإيبسلون ومن هنا لهنا بإيبسلون ومن
هنا لهنا بإيبسلون صح؟ اه كيف بيطلع معانا مين؟
بيطلع معانا R5 اللي هو هذا مش
حاجة هذا كلام كله يمكن أتمتته يعني ممكن can be
performed automatically by an algorithm اللي يتحول
من regular expression إلى فعلا NFA احنا خدنا صح من
ستة لواحد عشان يعمل مرة تانية؟ اه من ستة إلى واحد
عشان إيه نعم ارجعني إذا بدي أكرر ال regular
expression مرة فترة تلاتة يتكرر عدة مرات وهذا عشان
لو هي مش موجودة اطلاقا يعني هو ال zero المرة صح؟
الآن هذا ال R6 صح وبنقدر نكمل هذي R7 R7 هو نفس R6
بإضافة ال A فهو confrontation هذا ال R6 مع ال A بنتحه
عند نهاية ال R6 مع بداية تبع ال A وبنكمل بعدين
تمام فهذا الآن عملية الـ conversion أو الـ
constructing الـ NFA من ال .. من الـ regular
expression الآن نقدر نقول طيب okay هذا الـ NFA
بظبط لا يمكنني أن أبني منه لازم أشيل الـ
excellence هذه ولازم أتأكد أن مافي عندي استقرار
منها ال two edges في نفس ال label فنرجع الآن لـ الآن
عشان نعمل ال conversion بدنا نتفج على بعض
المصطلحات أنا في عندي هنا S مش في الأول لأول كانت
ال S وال T وال R يرمز إلى regular expressions
هنا ال S يرمز إلى state، صح؟ ال .. ال .. ال state
لو يمكنك أن تكون عندي state، ال state ها دي أنا ..
أنا الآن بتحاول أن أنا أفعلها دي فيه وارد جدا أن ال
state ها دي بيبقى فيه أسهم أو edges منها طالعة
الـ E الـ Epsilon closure of S هي كافة ال states
اللي من S عبر Epsilon اللي بوصل لها من S عبر Epsilon
set of NFA states reachable from S on E
transitions alone يعني لو لو عندي أنا هنا هو
نفسه هذا هذا هو تبع الـ نفس الـ expression هذا
النهائي شوفوا إيش الاختلاف أنه هيكون وصلنا هنا زاد
عليه الـ word لأن أنا لو أنا على state رقم واحد ف
الـ E closure of one يساوي مجموعة من الـ states اللي
هي أربعة و اثنين لأن لو من أربعة فيه كمان epsilon
هيك لو ثاني شوية أربعة
و اثنين الـ E closure الـ epsilon closure of ستة
مثلًا هي سبعة و واحد و برضه كمان أربعة و اثنين صح؟
لأنه من واحد بروح هيك و بروح هيك ده كله الـ E
closure الـ E closure في الخمسة و الخمسة هيك تشمل
.. تشمل إيش؟ ستة و تشمل سبعة و من ستة بروح لواحد و
بروح لأربعة و بروح لاثنين لحظة هنا إيش بيقول هنا الـ E
closure احنا بنعطيها state لكن ممكن نعطيها مجموعة
states هذا الـ braces تمثل مجموعة فهو هنا المجموعة
تحتوي على بس الخمسة بينما هنا المجموعة تحتوي على
الثلاثة وثمانية فإيش يعني لما نعطيها مجموعة states
يعني بدي الـ union تبعها الـ E closure تبع الثلاثة
مع الـ E closure تبع الثمانية واضح؟ أن هل الآن هذا
الآن هو عبارة عن بأخذوا الثلاثة لحالها الـ E
closure تبع الثلاثة إيش بيعطيني هون الثلاثة هاي
الثلاثة بس ستة صح لا ستة و سبعة صح الثلاثة لحالها
لا السادسة و الستة بتردنا على واحد اثنين و أربعة
صحيح اثنين و أربعة اثنين و أربعة اثنين و أربعة اثنين
و أربعة E closure تبع من قد الثمانية الثمانية الثمانية
الثمانية الثمانية الثمانية الثمانية
الثمانية الثمانية
الثمانية الثمانية الثمانية الثمانية الثمانية الثمانية
الـ E closure تبعت الثلاثة والثمانية شملت الثمانية
في تركيز صغير بس واحد شوية تبتدي الـ E closure تبعت
الثلاثة و تبعت الثمانية احنا
هيك أنا واحد اثنين واحد اثنين ثلاثة ثلاثة اه و
أخلي بالك احنا نبدأ يا يمكن برضه بضمن الثلاثة
بضمنهم اه بضمنهم هذا إذا كان إيش بضمنهم بضمنهم إذا
كان .. أيه نعم هي دائمًا موجودة الـ الـ الـ
state لحالها الـ safe لحال ذاتها موجودة ضمن اللي هو
إيش ضمن المجموعة .. مجموعة الـ closure تبعها خمسة
مش موجودة خمسة مش موجودة صح؟ مش موجودة هنا خليني
أطلع بس هي الـ الـ إمتى بتبقى موجودة و إمتى
بتبقى مش موجودة بس خلينا أولًا نرجع للجدل عشان نكمل
اللي بعد اللي بعد مش أكثر من أن هو لو عندي أنا T
هنا
احنا كلنا بيقول S عبارة عن single state T is a set
of states أصبحت الـ E closure تبع T is a set of
energy states reachable from S in E كل واحد من الـ
states from كل واحد من الـ states from كل واحد من
من الـ states from كل واحد من الـ states from كل
واحد من الـ states from كل واحد من الـ states from
كل واحد من الـ states from كل واحد من الـ states
from كل واحد من الـ states from كل واحد من الـ
states from كل واحد من الـ states from كل واحد من
واحد من الـ states from كل واحد من الـ states from
كل واحد من الـ states from كل واحد من الـ states
from
على أساس أنت بتعطيها single state و single input
بتعطيني من اللي ليش الـ state اللي بقى لكن لو
أعطيتها T يعني مجموعة من states بـ بـ أنا بأحكي
عن كافة الـ states اللي في هذا الـ set وين بـ وين
بروح منهم إذا معايا الـ A يعني تخيلي هذه الجدول تبع
الـ transition table هاي الـ A ليش حطيته تعمل هاي الـ
A وهي states مثلًا state 1, state 2, state 3, state
4, state 5 اللي مفترض جزء T تحتوي على الـ state
واحد و ثلاثة و واحد و ثلاثة و خمسة تمام فبنجد جدول
لو أنا في واحد و واحد هو على ايه و اين بيروح أنا
في ثلاثة و اين بيروح على خمسة و اين بيروح تمام فالـ
set هذا هو عبارة عن مجموعة الخلايا طبعًا بعمل محيط
لفاضي و أنا هتجدو الهدف أنا احنا هدفنا أنه نبدأ الـ
algorithm كتاب الـ algorithm تبدأ كتاب أنه بدنا
نبدأ من الـ start state احنا عندنا N فيه و نحو D
فيه هدفيني
أن أنا أطلع الجدول هدف جدول هدف في الأول يبدأ بالـ
start state S0 و أخرجه E closure تبعها يظهر معه
set الـ set هذا بدي أشوف لو دخل عليه الـ input
الفلاني وين هيوديني و لو دخل عليه فالـ
algorithm TG برجع نرجع للـ A هي أول شيء و هو E
closure of ZERO ZERO هي الـ start state بالنسبة للـ
figure اللي لدينا هذا يجتمع على الـ states دولة
هذا الـ set هو الـ set البداية و بنرمز له بالرمز a
الآن بدنا الـ move من a عبر من a Capital عبر a و
بدنا الـ move من a Capital عبر b هدول الآن عندي
عمودين بس لأن الـ alphabet اللي عندي في هذا الـ
example بس فيها الـ a و الـ b لو في كمان other input
symbols بنحط لكل واحد منهم عمود لأن أنا بعد ما جبت
الـ start set وسميته a هذا a هي اسم لهذًا بدي أحسب من
من هذول الـ states لو
أجهها input لو أجهها a وين بتوديني ف أنا
بدي أصبح الـ move من هذا الـ set تذكروا احنا الـ move
قلنا بنعرفها حالتين إما سيها هاي الـ a هو عبارة عن
هذول صح؟ هذه أول واحدة فيهم Zero لو أجها A و
بتوديني ما فيش ما فيش edge من Zero صح؟ هاي الـ Zero
ما فيش تمام؟ الآن one لو أجها A و بتوديني برضه
ما بتودنيش على أي مكان الاثنين الاثنين لو أجها A
بتوديني على ثلاثة أربعة لو أجها A ما فيشو سبعة سبعة
لو أجهها a ثمانية هذا الآن هو ناتج ثلاثة
و ثمانية دي
تران هذا الـ دي تران اتخيليها عبارة عن خلية في الـ
.. في الـ table ف أنا مشوفها هي عبارة عن الـ closure
الـ E closure تبع الـ move أول شيء الـ move تبع هذا هي
عبارة عن إيش الثلاثة و الثمانية لأن لو بتحسب الـ e
closure هذا الثلاثة و الثمانية عبارة عن set عبارة
عن إيش مجموعة احنا كنا نحكي في هذا الكلام لو أنا
عندي المجموعة هذه بتحسب الـ e closure تبعها إيش
يعني يعني أنا بأحسب من ثلاثة و ثمانية إيش فيه moves
عبر الـ epsilon وين بيودينا على أي stays بيطلع معايا
على الكلام أنا أولًا بدأت في الـ الـ E closure تبع
الـ zero stay الـ start zero الـ start zero طالع ليه
هدول اللي أنا بأحسب الـ move تبعهم على a وبعدها
هأحسب على b برضه الـ move تبع هدول على a الموضوع هذه
على a طلع ثلاثة و ثمانية تحسب الـ E closure ثلاثة و
ثمانية تطلع ثلاثة و ثمانية تطلع ثلاثة و ثمانية
تطلع ثلاثة و ثمانية تطلع
ثلاثة و ثمانية تطلع ثلاثة و ثمانية تطلع ثلاثة و
تطلع ثلاثة و ثمانية تطلع ثلاثة و ثمانية تطلع ثلاثة
تطلع ثلاثة و ثمانية تطلع
ثلاثة و ثمانية تطلع
ثلاثة و ثمانية
هذا الـ step الأولاني سميته A لو أي واحد من هذه الـ
states دخل عليها A هتودينها على أي واحد من هذه الـ
states لو دخل عليها B هتودينها على أي واحد من هذه
الـ states تبعهم هدول بأكرر الكلام هذا كله الآن الـ
B و الـ C هدول الـ B و الـ C هدول الـ B و الـ C هدول
الـ B و الـ C هدول الـ B و الـ C هدول الـ B و الـ C
هدول الـ B و الـ C هدول الـ B و الـ C و الـ move تبقى
الـ B مع الـ A لأن صدفت أن الـ move تبقى B مع الـ A
تعطي نفس المجموعة هذه وبالتالي هتطلع
معها الـ move of B مع A هتطلع معها المجموعة
المجموعة هذه هي نفسها هذه فلو بأعملش مجموعة باسم
جديد خلاص بأكتب بيه بينما B المفتاح بيه مع B بيطلع
لمجموعة أخرى و بأفرح سماها D تمام؟ بعدين راح باشر بأخذ
الـ C و حسب المفتاح بيها مع A و المفتاح بيها مع B
بيضلوا لحدين ما يخلص المجموعات .. بيضلش فيه
مجموعات جديدة بتتولد بيجفت يعني كل واحد من هدول
بيصبح هم في عزتهم states في الـ DFA و بشكل الـ DFA
هذا الآن بيصير Transition Table هذا بيصير
Transition Table بيجي بيقول هي الـ A الـ A هي الـ
start لو دخل عليها A small بتودين على B لو دخل
عليها B small بتودين على C صح؟ بيشكل الـ DFA من هذا
الـ Table المحاضرة جالسة الله بنرجع بنعيد على هذا
الكلام و بنبدأ في .. يعني هو عملينا أخر إشي بدنا يا
في ال lexical analysis فاحنا عموما الآن يا بنات
بنكون مرينا على التالي بنكون
في موضوع ال lexical analysis غطينا التالي
عطينا الـ role of the lexical analyzer عطينا ال
input buffering والـ specification of tokens ال
recognition of tokens الليكسيكال ال analyzer هذه
لم نضعه موش اه نرجع له أو نشوف tool تاني حكينا في
ال final automata والآن في المحاضرة هذه تقريبا
هذا ال section كله وضعناه اللي هو from regular
expressions to automata بدينا من regular
expressions to NFA بعدين من NFA إلى DFA الكلمة
المحاضرة اللي جاية بنجمل ال chapter هذا أيش اللي
ضال علينا منه وبنبدأ في chapter أربعة اللي هو ال
syntax analysis أو ال parsing يعطيكم العافية