We\'ve seen the union L_1 L_2, which includes any strings in L_1, L_2, or both,

Question

We've seen the union L_1 L_2, which includes any strings in L_1, L_2, or both, and we've seen the intersection L_1 L_2, which includes only strings that are in both L_1 and L_2. Now we consider another operator, the xor of L_1 and L_2, written as L_1 L_2. A string omega is included in L_1 L_2 only if it is included in either L_1 or L_2, but not both. For example, if L_1 = {a, ab} and L_2 = {a, bb}, L_1 L_2 = {ab, bb}. Given that DFA M_1; which recognizes L_1, is defined by the 5-tuple M_1 = {P, sigma, p_0, F_1, delta_1} and DFA M_2, which recognizes L_2, is defined by the 5-tuple M_2 = {Q, sigma, q_0, F_2, delta_2], give the formal 5-tuple that would define a machine M_3 which recognizes L_1 L_2.

Explanation / Answer

A deterministic nite automation DF A M1 isa 5-tuple { P, ,p0,F1,1}

Here in the given 5-tuple

P is a nite set called the states

nite set called the alphabet ,

And the 1 is the transition function of x P - >P

P0 is an element which in the set P

F1is subset of P is the set of accept states of the P..

Like wise

DFA M2 is { Q, ,q0,F2,2}

M2 is a 5-tuple Q is finite set called the states.

nite set called the alphabet ,

And the 2 is the transition function of x Q - >Q

Q0 is an element which in the set Q

M1 XOR M2 = M3

So if we compute the M1 XOR M2

By observing the M1 and M2 there are only a finite alphabet set is common in both sets.

And remaining all are not in common.

M3 = { P,Q,p0,q0,F1,F2, 1, 2}

P0 is belongs to P and q0 is belongs to Q

So M3={ P,Q,F1,F2, 1, 2}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.