Suppose we have an alphabet consisting of two symbols, {0, 1}, and we want to construct a machine that accepts all strings that end with "01". Here is how we can construct the DFA and NFA for this language:
DFA:
- Q = {q0, q1, q2} (set of states)
- Σ = {0, 1} (alphabet)
- δ = (q0, 0) → q0; (q0, 1) → q1; (q1, 0) → q0; (q1, 1) → q2; (q2, 0) → q0; (q2, 1) → q1 (transition function)
- q0 = initial state (start state)
- F = {q1} (set of accepting states)
This DFA has three states and accepts any string that ends with "01". For example, the input string "11001" would be accepted by the DFA, as it ends with "01".
NFA:
- Q = {q0, q1} (set of states)
- Σ = {0, 1} (alphabet)
- δ = (q0, 0) → q0; (q0, 1) → {q0, q1}; (q1, 0) → q0; (q1, 1) → q1 (transition function)
- q0 = initial state (start state)
- F = {q1} (set of accepting states)
This NFA has two states and accepts any string that ends with "01". The key difference is that in the transition function for input symbol "1", the NFA can transition to both q0 and q1 simultaneously. This means that the NFA can be in multiple states at once, while the DFA can only be in one state at a time.
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন