Report

2 DFA VERSUS NORMAL DFA Pavan Kumar Akulakrishna (M.Tech, SERC) SR No: 06-02-01-10-51-12-1-09469 Under Guidance of : Prof. Deepak D’souza. FUNDAMENTAL QUESTION Is 2 way DFA more powerful than a one way DFA? “OR” Does the ability to do multiple scans on the tape gives rise to an increase in ‘POWER’ of the 2DFA? Not Intuitively clear! Need to develop a formal model. UNDERSTANDING THE 2DFA BEHAVIOR Consider a String w: which is broken down into two parts say x and z. x z Right to Left Q Left to Right P If next time Right to Left Q, then Left to Right will be P. i.e., Tx (Q)=P If never emerges? Let Tx (Q) = ┴ The first time it emerges from x without having been to z. Call the state Tx(.). CONSTRUCTING A TABLE Tx (q) depends only on x and q. Write down Tx(q) for all possible states q • T: (Q U {.}) (Q U {┴}) Possible such tables taking |Q| = k are, (k+1)^(k+1). Hence, a finite information can be passed. Q1 Q1 Qk . ……. Qk ┴ √ Q2 …… Q2 √ √ …….. √ √ USING MYHILL NERODE THEOREM • If there are tables Tx == Ty and M accepts xz. Then, yz is also said to be accepted. Let L(M) denote the language accepted by the machine. Define a Equivalence relation on strings x and y: If Tx = Ty, x ≡L(M) y. PROPERTIES OF ≡L(M) Right congruence, • x ≡L(M) y then xa ≡L(M) ya Refines L(M) • If Tx = Ty , either both x and y accepted or rejected. Finite Index • No. of Equivalence classes = No. of Unique Tables [i.e., (k+1)^(k+1)]. Hence, by Myhill-Nerode theorem, L(M) is a Regular Language. INFERENCES DRAWN A 2DFA is NO more powerful than a normal DFA We can construct a one way DFA equivalent to a 2 DFA viz. • Indentify equivalence classes. • Use construction defined by ≡ M≡ CONSTRUCTING EQUIVALENT DFA Formally, a DFA equivalent to 2 DFA looks as: D=(Q’,S’,Σ U{├, ┤}, δ,F’) Q’ = { T: (Q U {.}) (Q U {┴}) } S’ = Tε δ (Tx, a) = Txa F’ = {Tx | x Є L(M) } ADVANTAGES OF 2 DFA A 2DFA is more compact than a DFA • i.e., L(M)= {x Є {a, b}* | #a(x) is multiple of 7 and #b(x) is multiple of 5} Normal DFA would have 35 states. 2 DFA can be constructed using 14 states, including the accept and reject states (t, r). • • • • A 2DFA has single accept and reject states Whereas, a DFA may have multiple final states. E.g. L(M) = {x Є {a, b}* | #a(x) is multiple of 7 or #b(x) is multiple of 5}. Normal DFA has 12 final states. CONCLUSIONS 2 way DFA is a convenient representation for some regular languages, much like NFA Converting it to a normal DFA can be tedious as it involves constructing and identifying identical tables.