تحويل NFA إلى DFA وفهم اللاحتمية في الحوسبة 🤖

Computation 11 NFA to DFA
نظرية الحوسبه
دكتور نذيرغرايبه

1:03 in Linz: page 63: Why Nondeterminism?
3:04 CS 341: Chapter 1 Slide 40 What happens on input string 010110 ?
without reading an input symbol, NFA splits into multiple copies
Each copy proceeds independently of other copies.NFA follows all possible paths in parallel.
تنقسم NFA
إلى نسخ متعددة ، وتتابع كل نسخة بشكل مستقل عن النسخ الأخرى ، وتتبع
NFA
جميع المسارات الممكنة بالتوازي.

https://web.njit.edu/~marvin/cs341/notes/chap01-handout4.pdf
11:21 backtracking.in DSA and AI, XO, and Chess (game-playing program)
22:28 Look at the NFA in Figure 2.8
24:57 nondeterminism is an effective mechanism even in CFG
26:31 Finally, there is a technical reason for introducing nondeterminism

28:40 NFA to DFA
31:10 example 1
45:28 example 2
53:14 Easier Method طريقه اسهل :
1:00:30 in the new table that consists of 2^n states, we have to consider only the accessible states in building the new DFA

1:05:00 Homework
1:07:30 More Examples
1:12:15 Homework