انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة
الكلية كلية تكنولوجيا المعلومات
القسم قسم البرامجيات
المرحلة 2
أستاذ المادة حازم جليل حسن ابو رغيف
25/10/2013 09:09:36
Nondeterminism is a useful concept that has great impact on the theory of computation. When the machine is in a given state and reads the next input symbol, we know what the next state will be -it is determined this called deterministic computation but in a nondeterministic machine, several choices may exit for the next state at any point. Nondeterminism is a generalization of determinism ,so every deterministic finite automaton is automatically a nondeterministic finite automaton. The different between a deterministic finite automation and a nondeterministic finite automaton. 1- every state of always has exactly one exiting transition arrow for each symbol in the alphabet but the nondeterministic violates that rule. 2-In DFA, label on the transition arrow are symbols from the alphabet .this NFA has an arrow with the label ? , an NFA may have arrows labeled with members of alphabet or ?. Zero, one , or many arrows may exit from each state with the label ? Nondeterminism may be viewed as a kind of parallel computation wherein multiple independent "processes" or "thread" can be running concurrently. when the NFA splits to following several choices, that corresponds to a process "forking" into sveral children, each proceeding separately. if at least one of these processes accepts, then te entire computation accepts. Another way to think of a nondeterministic computation is as tree of possibilities. the root of the tree corresponds to the start of the computation. Every branching point in the tree corresponds to a point in the computation at which the machine has multiple choices. the machine accepts if at least one of the computation branches ends in an accept state. as show below.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|