مناقشة الأوتومات واللغات الصورية

[Maya]

[Mu_Nizar]

سؤال لو سمحتم ..
بالكتاب صفحة 46:
السؤال الثامن: كيف نبرهن صحة العلاقة الثالثة ؟
السؤال التاسع :
العلاقة الأولى صحيحة , الثانية و الثالثة خطأ ؟ أليس كذلك ؟

[Maya]

[Yamen Ali]

[Mu_Nizar]

سؤال غريب شوي
بفرض:
A <=> B
B <=> C
C <=> D
SO: A,B,C,D are Equivalent Classes
and the Index of this Equivalent Relationship =4
+
و نستطيع القول أن الـ index لأي علاقة تكافؤ هو حتما أكبرأو يساوي 2
؟

[farah_online]

هلأ القواعد الأحادية بحذفها بجميع الحالات إلا إذا كان في بالقاعدة عودة مو هيك ؟؟

[Gardenia]

سؤال آلة تورينغ أكيد مو داخلة معنا ؟؟

[N.Sham]

[العقاب 210]

خوارزمية (CYK) هل نحن مطالبون بها؟

[life moon]

[the master]

مرحبا يا جماعة..
اذا ممكن سؤال بتوطئة الضخ تبع خارج السياق، عنا هي اللغة يلي مثبت انو هي خارج السياق، وفي السلسلة يلي تحتا z هي لازم تنتمي للغة:
pumping lemma.jpg
هلأ لما ناخد i=2 لازم نضخ v مرتين وكمان x مرتين، طيب بهالحالة رح تصير السلسلة z هي: aaaaabbbb !
شو مشان ساعتها ما بتنتمي للغة وبتصير هي اللغة مانا خارج السياق؟ حدا عندو فكرة ليش؟
إلها علاقة بإنو v ما لازم يكون هيك وضعها أو الشغلة إلها علاقة بشروط الضخ؟؟
هلأ طيب سؤالي كمان نحنا بتوطئة الضخ تبع اللغات المنتظمة كانت n هي عدد حالات الأوتومات المنتهي الحتمي الأصغري (يخزي العين على هالاسم شو حلو )، طيب هون بخارج السياق شو بتمثل n؟؟
وشكراً

[Pure Man]

[the master]

[Maya]

[Yamen Ali]

[the master]

[shashi]

[محمود كشكش]

شباب سؤال بس:
شو هوة الريغيولار اكسبريشن للغة يلي بتقبل اي سلاسل من الاصفار و الواحدات بس بشرط يكون عدد الاصفار يساوي عدد الواحدات ... يعني مثلا :
aaabbb , ababab , aaabbbabab , bababbaa , .........

[Yamen Ali]

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

في طريقة حلوة للتفكير بتوطئة الضخ بكتاب ( introduction to automata ) يمكن توضح الالتباس يلي عم بصير .
لنفرض في لاعبين ( لاعب أول - لاعب ثاني ) .
*- اللاعب الأول بيختار لغة حتى يثبت أنها غير منتظمة .
*- اللاعب الثاني بيختار ( n ) يعني أي عدد بيخطر على باله .
*- اللاعب الأوّل بيختار سلسلة تنتمي للغة طولها أكبر من ( n ) ( الفكرة هون ان اللاعب الأوّل ما بيعرف العدد يلي اختاره اللاعب الثاني مشان هيك لازم يختار سلسلته بحيث تكون محقّقة من اجل أي عدد ممكن و هي الفكرة يلي حطيتها قبل شوي يعني نحن بنختار السلسلة عملياً بحيث تحقّق المطلوب بغض النظر عن ثابت التوطئة ) .
*- اللاعب الثاني يقسّم السلسلة التي اختارها اللاعب الأول بطريقة ما . ( وفق شروط توطئة الضخ ) .
*- إذا قدر اللاعب الأولّ يوجد قيمة لـ i بحيث تخرج السلسلة من اللغة مهما كان التقسيم الذي اختاره اللاعب الثاني عندئذ يربح اللاعب الأول أي يثبت أن اللغة غير منتظمة . ( و هي الفكرة من إيجاد جميع التقاسيم الممكنة يعني أنا أي تقسيم بعطيك ياه لازم تقدر توجد قيمة واحدة لـ i على الأقل بحيث تخرج السلسلة من اللغة . )
و في فكرة تانية ( رأي شخصي ) أن نحن عملياً لما بنشتغل على توطئة الضخ و بنختار سلسلة
الأدق أن ما تكون سلسلة ثابتة يعني لما نختار ( a^nb^n ) بحيث يكون n هو ثابت التوطئة و بشتغل على توطئة الضخ من اجل هي السلسلة بكون ادق من اختيار سلسلة ثابتة (aaabbb ) و الشغل عليها لأن بالأصل في بنفي توطئة الضخ مهما يكن ( n ) يعني مشان نلتزم بنص النظرية ( مرة ثانية هذا رأي شخصي مو اكثر ) .

[N.Sham]

هلأ مثال الاوتومات بمكدس اللي مشروح بالمحاضرة بنوطة المستقبل .. مافهمت كيف صارت القصة بمكدس واحد .. ياريت ازا حدا فهمانا بس يشرحلنا شوي عنا