Question

In: Computer Science

Let M be defined as follows M = (K, Σ, s, ∆, F ) for K...

Let M be defined as follows M = (K, Σ, s, ∆, F ) for K = {q0, q1, q2, q3, }, s = q0, Σ = {a, b, c}, F = {q0, q2, q3} and ∆ = {(q0, abc, q0), (q0, a, q1), (q0, e, q3), (q1, bc, q1), (q1, b, q2), (q2, a, q2), (q2, b, q3), (q3, a, q3)}.

1. (1pts) Draw the diagram of M

2. (6pts ) DRAW a diagram of an automata M0 such that M0 ≡ M and M0 and M0 is defined by the BOOK definition.

3. (3pts) List all components of M0 = (K 0 , Σ 0 , s 0 , ∆, 0 F 0 )

Expert Solution

M = (K, Σ, s, ∆, F ) for

K = {q0, q1, q2, q3, } (Set of all states )

s = q0 (Starting state)

Σ = {a, b, c} (Set of inputs )

F = {q0, q2, q3} (Set of final states )

∆ = {(q0, abc, q0), (q0, a, q1), (q0, e, q3), (q1, bc, q1), (q1, b, q2), (q2, a, q2), (q2, b, q3), (q3, a, q3)}

(Transition function that a state on getting certain input goes to which state )

It is a NFA by seeing the transition function we can see that q1 on getting a goes to no where it implies it is NFA

1) So Diagram on the basis of above information is :->

2) Finding M0 (DFA) that is equivalent to M (NFA) as you have not provided what M0 is So i am considering it as DFA which will be equivalent to given NFA

Below Snaps shows you how to convert NFA to its euivalent DFA

venereology answered 1 year ago

Given a non-deterministic automaton M = (K, Σ, s, ∆, F ) for K = {q0,...

Given a non-deterministic automaton M = (K, Σ, s, ∆, F ) for K = {q0, q1, q2, q3}, s = q0, Σ = {a, b}, F = {q1, q2, q3}, and ∆ = {(q0, a, q1), (q0, b, q3), (q1, a, q2), (q1, b, q1), (q3, a, q3), (q3, b, q2)} 1. (1pts) Draw the diagram of M 2. (2pts) Explain why M is not deterministic 3 (5pts) DRAW a diagram of a deterministic M0 such that M ≈...

Let S = {2 k : k ∈ Z}. Let R be a relation defined on...

Let S = {2 k : k ∈ Z}. Let R be a relation defined on Q− {0} by x R y if x y ∈ S. Prove that R is an equivalence relation. Determine the equivalence class

Let f be an irreducible polynomial of degree n over K, and let Σ be the...

Let f be an irreducible polynomial of degree n over K, and let Σ be the splitting field for f over K. Show that [Σ : K] divides n!.

Let f : Z × Z → Z be defined by f(n, m) = n −...

Let f : Z × Z → Z be defined by f(n, m) = n − m a. Is this function one to one? Prove your result. b. Is this function onto Z? Prove your result

Let M/F and K/F be Galois extensions with Galois groups G = Gal(M/F) and H =...

Let M/F and K/F be Galois extensions with Galois groups G = Gal(M/F) and H = Gal(K/F). Since M/F is Galois, and K/F is a field extension, we have the composite extension field K M. Show that σ → (σ|M , σ|K) is a homomorphism from Gal(K M/F) to G × H, and that it is one-to-one. [As in the notes, σ|X means the restriction of the map σ to the subset X of its domain.]

Theorem: Let K/F be a field extension and let a ∈ K be algebraic over F....

Theorem: Let K/F be a field extension and let a ∈ K be algebraic over F. If deg(mF,a(x)) = n, then 1. F[a] = F(a). 2. [F(a) : F] = n, and 3. {1, a, a2 , ..., an−1} is a basis for F(a).

Let a < c < b, and let f be defined on [a,b]. Show that f...

Let a < c < b, and let f be defined on [a,b]. Show that f ∈ R[a,b] if and only if f ∈ R[a, c] and f ∈ R[c, b]. Moreover, Integral a,b f = integral a,c f + integral c,b f .

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show...

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show that it is an equivalent relation Find the number of different equivalent classes and write all of them

Let (F, <) be an ordered field, let S be a nonempty subset of F, let...

Let (F, <) be an ordered field, let S be a nonempty subset of F, let c ∈ F, and for purposes of this problem let cS = {cx | x ∈ S}. (Do not use this notation outside this problem without defining what you mean by the notation.) Assume that c > 0. (i) Show that an element b ∈ F is an upper bound for S if and only if cb is an upper bound for cS. (ii)...

(a) Let M be a Cr submanifold of Rn, and let f : M → R...

(a) Let M be a Cr submanifold of Rn, and let f : M → R be a Cr function. Show there is an open neighbourhood V of M in Rn and a Cr function g : V → R such that f = g|M. (b) Show that, if M is a closed subset of Rn, then we can take V = Rn . (c) Can we take V = Rn in general? Why or why not? We've just learned...