انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة
الكلية كلية العلوم للبنات
القسم قسم الحاسبات
المرحلة 2
أستاذ المادة محمد عبيد مهدي الجبوري
28/05/2018 19:38:16
Equivalence of PDAs and CFGs
A language is context iff some PDA recognize it
If L=L(G) for some CFG G, then L=L(M) for some PDA M.
Proof idea
* Need to show that given CFG G, we can find PDA M that recognize the same language
G generates.
* Basic idea is to build PDA that simulates a leftmost derivation.
* For example, consider CFG G=(V,?,R,S)
Variables V= {S}
Terminales ?={0,1}
Rules R= S?0S0S| 1S0| 1
* Leftmost derivation of string 010110 ? L(G)
S?0S0S?010S?0101S0?010110
Creat PDA for CFG as follow:
Equivalence of PDAs and CFGs
A language is context iff some PDA recognize it
If L=L(G) for some CFG G, then L=L(M) for some PDA M.
Proof idea
* Need to show that given CFG G, we can find PDA M that recognize the same language
G generates.
* Basic idea is to build PDA that simulates a leftmost derivation.
* For example, consider CFG G=(V,?,R,S)
Variables V= {S}
Terminales ?={0,1}
Rules R= S?0S0S| 1S0| 1
* Leftmost derivation of string 010110 ? L(G)
S?0S0S?010S?0101S0?010110
Creat PDA for CFG as follow:
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم
|