Full transcript
0:02مرحباً أصدقائي ،
0:03أهلاً بكم في قناتنا .
0:05في هذه الجلسة ، سنناقش
0:07كيفية بناء قواعد
0:09نحوية منتظمة من تعبير
0:11منتظم . حسناً ؟ ما هو
0:13المدخل ؟ المدخل هو
0:14عبارة عن تعبير منتظم .
0:17علينا تحويل التعبير
0:18المنتظم إلى قواعد
0:20نحوية منتظمة . ما هي
0:22الإجراءات ؟ الإجراءات
0:24بسيطة جداً . أولاً ، من
0:26التعبير المنتظم
0:27المعطى ، عليك بناء آلة
0:29الحالة المنتهية غير
0:31الحتمية ( NFA ) . علينا
0:34بناء NFA مع إبسيلون . NFA
0:37مع إبسيلون . حسناً ؟ من
0:40هذه الـ NFA ، الآن ما
0:43هذا ؟ حذف احذف جميع
0:48انتقالات إبسيلون .
0:51احذف جميع انتقالات
0:53إبسيلون وحولها إلى
0:55آلة حالة منتهية حتمية
0:58( DFA ) مكافئة . حول الـ NFA
1:01إلى DFA مكافئة . أي بدون
1:04إبسيلون ، بدون
1:06إبسيلون . الآن ، الخطوة
1:10الثالثة هي التحويل من
1:12هذه الـ DFA إلى قواعد
1:14نحوية منتظمة . أعتقد
1:17أن الجميع يعرف إجراء
1:19كيفية بناء القواعد
1:21النحوية المنتظمة من
1:22الآلة المنتهية .
1:24ببساطة ، تصبح الحالات
1:26في الآلة المنتهية هي
1:28الرموز غير الطرفية .
1:31تصبح الحالة هي الرموز
1:33غير الطرفية . وهنا ،
1:36تصبح الانتقالات في
1:38الآلة المنتهية هي
1:40الإنتاجيات . حسناً ؟ ما
1:43هي الإجراءات ؟
1:44الإجراءات ببساطة هي
1:45أنهم يعطونك تعبيراً
1:47منتظماً . الخطوة
1:48الأولى ، تحويل
1:49التعبير المنتظم . أي
1:51علينا بناء NFA مع
1:52انتقال إبسيلون . الآن
1:54الخطوة التالية هي حذف
1:56جميع انتقالات
1:57إبسيلون وتحويلها إلى
1:59DFA . ومن ثم من الـ DFA
2:00عليك التحويل إلى
2:02قواعد نحوية منتظمة .
2:03الإجراء هو أن تصبح
2:05الحالات في الـ DFA
2:06رموزاً غير طرفية
2:07وتصبح الانتقالات
2:08إنتاجيات . هذا هو
2:10إجراء الإنتاج . الآن
2:11سنناقش مثالاً أيضاً .
2:14لنفترض أن هذا هو
2:16تعبير منتظم ( A star B A plus
2:19B ) . لنفترض أن هذا هو
2:21التعبير المنتظم . كيف
2:24نحول ؟ إجراء بسيط . Q
2:28صفر . في البداية يتم
2:30كتابة التعبير
2:31المنتظم ( A star B A plus B )
2:37الكل star QF . إذاً هذه هي
2:40الحالة الابتدائية .
2:42وهذه هي الحالة
2:43النهائية . قم بتوسيع
2:45التعبير خطوة بخطوة . Q
2:47صفر A star ، هذه حالة
2:50واحدة . B ، هذه حالة
2:54أخرى . A plus B الكل star إلى
3:00QF الآن ، يتم تحويل A star
3:03هكذا : Q صفر . أعتقد أن A
3:08star تعني إما صفر أو
3:10تكرارات كثيرة لـ A ، أي
3:12صفر أو تكرارات كثيرة ،
3:14مما يعني حلقة ذاتية .
3:19هذا هو إنتاج A star . يتم
3:22استبدال A star بهذا .
3:25الآن ، B بالمثل ،
3:27استبدل A plus B الكل star ،
3:29هذا أيضاً نفس
3:30الإبسيلون . A plus B تعني
3:33إما A أو B ، أنت تعرف
3:35رمز الجمع ، الجمع يعني
3:37إما A أو B ، وانتقل
3:39مجدداً إلى إبسيلون .
3:42هذه NFA مع إنتاج
3:43إبسيلون . الآن ، ماذا
3:45نفعل خطوة بخطوة ؟ تخلص
3:47ببساطة من إبسيلون
3:49واكتب الـ DFA المقابل
3:51من Q naught هذه . إذا كنت
3:55تستبدل إبسيلون ، فإن A
3:57تنتقل ببساطة إلى
3:59الحلقة الذاتية ( self-loop )
4:01وعند إدخال B إلى Q F.
4:03وأخيراً ، وصلنا إلى
4:05الحالة النهائية بـ A و
4:07B. لاحظ أن هذا هو الـ DFA
4:10للتعبير النمطي
4:11المعطى . الآن ، ما هي
4:14الحالات التي لدينا ؟
4:17الحالات تساوي Q naught و Q
4:19F. Q naught و Q F. ما هي
4:21المدخلات ؟ المدخلات
4:25تساوي A و B. حسناً ؟ ما
4:27هي الإنتاجات التي
4:29لدينا ؟ دلتا عند Q naught
4:31و A تساوي Q naught . دلتا لـ
4:36Q naught عند B تساوي qf .
4:40وبالمثل ، دلتا لـ qf
4:42عند A تساوي qf . دلتا لـ
4:46qf عند B تساوي qf . هذه هي
4:49الحالة الابتدائية و Q
4:51naught هي الحالة
4:52الابتدائية . Qf هي
4:55الحالة النهائية . الآن
4:57، ما هو الإجراء ؟ من
4:59هذه الأوتوماتا
5:00المحدودة ، يجب عليك
5:02تحويل التعبير النمطي
5:04من هذه الأوتوماتا
5:05المحدودة إلى قواعد
5:07نمطية . إذن ، ما هي
5:08القواعد ؟ G تساوي V و T و
5:11P و S. V هي الرموز غير
5:13النهائية ( non-terminals ) .
5:15إذن ، ما هي الرموز غير
5:16النهائية ؟ الحالات في
5:19الأوتوماتا المحدودة q
5:21naught و qf . هاتان هما
5:23الرموز غير النهائية . T
5:24، ما هي الرموز
5:26النهائية ( terminals ) ؟
5:27المدخلات في
5:28الأوتوماتا المحدودة ،
5:30وهي A و B. نعم ، S هي رمز
5:32البداية . ما هو رمز
5:34البداية ؟ Q0 . و P. ما هي P
5:37؟ الإنتاجات .
5:39الانتقالات هنا تسمى
5:41إنتاجات . لذا ، اكتب
5:43الانتقال ببساطة . Q0
5:45تؤدي إلى ، أي أن Q0 عند A
5:48تنتقل إلى Q0 . هذه هي
5:51المعادلة . Q0 تؤدي إلى
5:55AQ0 . Q0 تؤدي إلى B QF . الآن
6:01، وإلى جانب Q0 تؤدي إلى
6:04B ، نحن ننتقل إلى
6:05الحالة النهائية
6:07أيضاً . عند Q0 مع B ، نحن
6:10ننتقل إلى الحالة
6:12النهائية . إذا انتقلت
6:13إلى الحالة النهائية ،
6:15يمكنك كتابة هذا
6:16المصطلح أيضاً . أي
6:18بدون حالة . وبالمثل ، QF
6:21عند A تنتقل إلى QF . QF
6:25إلى A أيضاً . لأنه
6:28لماذا ؟ نحن ننتقل إلى
6:30الحالة النهائية .
6:31وبالمثل ، QF إلى B تنتقل
6:34إلى BQF . QF إلى B. هذه هي
6:38القواعد النمطية من
6:39التعبيرات النمطية
6:41المعطاة . الإجراء بسيط
6:43للغاية . التحويل إلى DFA
6:45ومن DFA إلى أوتوماتا
6:47محدودة . تحويل
6:48الأوتوماتا المحدودة
6:50DFA إلى قواعد نمطية .
6:51شكراً لك .