انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

Convert NDFA into DFSA

الكلية كلية العلوم للبنات     القسم قسم الحاسبات     المرحلة 2
أستاذ المادة محمد عبيد مهدي الجبوري       28/05/2018 19:29:40
Construct an equivalent DFA from NFA:

Every DFA is an NFA, it is clear that the class of languages accepted by NFA’s includes the languages accepted by DFA’s.
To convert NFA to DFA we can carry out the following algorithm:
1- Begin with {q0}, start state, and calculate ?({q0},a) for all a in ? this gives a number of new states Q-.
2- For each new states Q-, we again calculate ?(Q-,a) for all a in ? and introduce new states if necessary.
3- Repeat step2 until there are no new states.
4- Final states of new DFA are the states that contain any final state of the previous NFA.
Example:
Convert the following NFSA into equivalent FSA
Construct an equivalent DFA from NFA:

Every DFA is an NFA, it is clear that the class of languages accepted by NFA’s includes the languages accepted by DFA’s.
To convert NFA to DFA we can carry out the following algorithm:
1- Begin with {q0}, start state, and calculate ?({q0},a) for all a in ? this gives a number of new states Q-.
2- For each new states Q-, we again calculate ?(Q-,a) for all a in ? and introduce new states if necessary.
3- Repeat step2 until there are no new states.
4- Final states of new DFA are the states that contain any final state of the previous NFA.
Example:
Convert the following NFSA into equivalent FSA


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .