Example of closure
Constructing the equivalent DFA
Let Mn = (Q, Σ, δ, s, F) be any NFA. We construct the DFA Md =(2Q, Σ, δ', E(s), F'), here :
![573_Example of closure.png](https://www.expertsmind.com/../CMSImages/573_Example of closure.png)
E(q0)
|
E(q1)
|
E(q2)
|
E(q3)
|
E(q4)
|
q0, q1, q2, q3
|
q1, q2, q3
|
q2
|
q3
|
q3,q4
|
Prove property of δ and δ'
Let Mn = (Q, Σ, δ, s, F) be any NFA, and Md = (2Q, Σ, δ', E(s), F') be a DFA, where
![2143_Example of closure1.png](https://www.expertsmind.com/../CMSImages/2143_Example of closure1.png)
Prove
by induction.
Prove a general statement
![1014_Example of closure11.png](https://www.expertsmind.com/CMSImages/1014_Example%20of%20closure11.png)
Proof
Part I:
For any string w in Σ*, and states q and r in Q, there is R ⊆ Q so that
![1827_Example of closure2.png](https://www.expertsmind.com/../CMSImages/1827_Example of closure2.png)
Basis:
Let ω be a string in Σ*, q and r be states in Q, and (q, w) -|*Mn (r, ε) in 0 step. Because (q, w) -|*Mn (r, ε) in 0 step, we know (1) q=r , and (2) w= ε.
Then, (E(q), w) = (E(r), ε).
Thus, (E(q), w) -|*Md (E(r), ε) .
That is, there exists R=E(r) such that r ∈ R and (E(q),w) -|*Md (R, ε). Induction hypothesis:
For any non-negative integer k, string w in Σ*, and states q and r in Q, there is R⊆Q:
![1081_Example of closure4.png](https://www.expertsmind.com/../CMSImages/1081_Example of closure4.png)
Induction step:
Prove, for any non-negative integer k, string w in Σ*, and states q and r in Q, there exists R ⊆ Q:
![112_Example of closure5.png](https://www.expertsmind.com/../CMSImages/112_Example of closure5.png)
Let w be a string in Σ*, q and r be states in Q, and (q, w) -|*Mn (r, ε) in k+1 steps.
Because (q, w) -|*Mn (r, ε) in k+1 steps and k≥0, there exists a state p in Q and a string ∈aΣ* so that (q, w) -|*Mn (p, a) in k steps and (p, a) -|Mn (r, ε) for some a∈Σ∪{ε}.
From the induction hypothesis and (q, w) -|*Mn (p, a) in k steps, we know that there exists P⊆Q so that (E(q), w) -|*Md (P, a) and p∈P. Since (p, a) -|Mn (r, ε), rδ∈(p, a).
From definition of δ' of Md, E(δ(p, a))⊆δ'(P, a) as p∈P.
Because rδ∈(p, a) and E(d(p, a))⊆δ'(P, a), r'δ∈(P, a).
![1415_Example of closure12.png](https://www.expertsmind.com/CMSImages/1415_Example%20of%20closure12.png)
Part II:
For any string w in Σ*, and states q and r in Q, there exists R ⊆ Q such that r∈R and
![735_Example of closure6.png](https://www.expertsmind.com/../CMSImages/735_Example of closure6.png)
Proof
Basis:
Let w be a string in Σ*, q and r be states in Q, R be a subset of Q such that r ∈ R and
![2221_Example of closure13.png](https://www.expertsmind.com/CMSImages/2221_Example%20of%20closure13.png)
Because (E(q),w) -|*Md (R, ε) in 0 step, E(q)=R and ω=ε.
From the definition of E, δ'(q, ε)=R because E(q)=R. Then, for any r∈R, (q, ω) -|*Mn (r, ε).
That is, there exists R=E(q) such that r ∈ R and (q, ω) -|*Mn (r, ε). Induction hypothesis:
For any non-negative integer k, string w in Σ*, and states q and r in Q, there exists R⊆Q such that r∈R and:
![1001_Example of closure7.png](https://www.expertsmind.com/../CMSImages/1001_Example of closure7.png)
Prove, for any non-negative integer k, string w in Σ*, and states q and r in Q, there exists R ⊆ Q such that r∈R:
![1894_Example of closure8.png](https://www.expertsmind.com/../CMSImages/1894_Example of closure8.png)
Let w be a string in Σ*, q and r be states in Q, and (E(q), w) -|*Md (R, ε) in k+1 steps.
Because (E(q), w) -|*Md (R, ε) in k+1 steps and k≥0, there exists P∈2Q (i.e. P⊆Q) and a string ∈aΣ* such that ω=aa, (E(q), a) -|*Md (P,ε) in k steps and (P, a) -|Md (R, ε) for some a∈Σ.
From the induction hypothesis and (E(q), a) -|*Md (P, ε) in k steps, we know that there exists p∈P such that (q, a)-|*Mn(p,ε) (i.e. (q, aa) -|*Mn (p, a) ).
Since (P, a) -|Md (R, ε), there exists r∈R such that r= δ(p, a).
Then, for some r∈R, (p, a) -|*Mn (r, ε).
Thus, (q, w) -|*Mn (p, a) -|*Mn (r, ε) for some r∈R.
Email based Automata assignment help – homework help
The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help – Automata homework help and online tutoring with best qualified and experienced computer science tutor’s help. We cover all topics including Example of closure in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.