write the dfa for Let L={w in {0,1}*| w is a binary number that is a...

write the dfa for Let L={w in {0,1}*| w is a binary number that is a multiple of 4}

Solutions

Expert Solution

// I HOPE I COULD HELP

// IN CASE OF ANY QUERY FEEL FREE TO COMMENT AND ASK

final state=q0

non-final state=q1,q2,q3

The state transition diagram drawn below will accept all strings over {0,1} which when interpreted are multiples of 4.

If any number is not divisible by 4 and leaves 1 as a remainder the control will move on to state q1.
If any number is not divisible by 4 and at the same time on dividing leaves 2 as a remainder the control will move on to state q2.
If any number is not divisible by 4 and leaves 3 as remainder the control moves to q3.
If the number is divisible by 4 that means that the number is a multiple of 4 the control will go to q0.

On testing on the inputs 0 it will get accepted as it is a multiple of 4, 01 will not be accepted by the dfa, 10 will leave remainder as 2 hence again not accepted, 11 will leave remainder as 3 hence not accepted and will end on q3, 100 will be accepted by the dfa at state q0 as it is a multiple of 4.

venereology answered 4 months ago

Next > < Previous

Related Solutions

- Give state diagram of DFA recognizing L={w | w is 0,1-string, and contains 3k 0s...

- Give state diagram of DFA recognizing L={w | w is 0,1-string, and contains 3k 0s and 2m 1s for some integers k and m at least 0}. For examples, 0010111 is in L, but 010011 is not in L. The first string contains 3 0s and 4=2x2 1s, but the second string has an odd number of 1s.

Draw an NFA for the following language then convert to a DFA: L = {w :...

Draw an NFA for the following language then convert to a DFA: L = {w : |w| is odd or |w| is a multiple of 4} where Σ = {0, 1}

Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to...

Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to be f(x1x2…xk)=x2x3…xkx1. That is, f takes the first bit of a string x and moves it to the end of x, so for example a string 100becomes 001; if |x|≤1, then f(x)=x Also, suppose that g:{0,1}∗→{0,1}∗ is a function such that g(x1…xk)=0x1…xk (that is, gg puts an extra 0 in front of the given string, so for example g(100)=0100. Everywhere in this question we...

Let L ⊆ Σ ∗ and define S(L), the suffix-language of L, as S(L) = {w...

Let L ⊆ Σ ∗ and define S(L), the suffix-language of L, as S(L) = {w ∈ Σ ∗ | x = yw for some x ∈ L, y ∈ Σ ∗ } Show that if L is regular, then S(L) is also regular.

w = 50,000 + 10,000L where w is wages, L is the number of players The...

w = 50,000 + 10,000L where w is wages, L is the number of players The demand for players is given by the Marginal Revenue Product: MRP = 500,000 – 20,000L The Marginal Factor Cost to the club is : MFC = $50,000 + 25,000L If the NFL labor market were competitive, what would be the equilibrium number of players employed? If the NFL labor market were competitive, what would be the equilibrium wage of a player? We know that...

Let ? and ? be two independent uniform random variables such that ?∼????(0,1) and ?∼????(0,1). A)...

Let ? and ? be two independent uniform random variables such that ?∼????(0,1) and ?∼????(0,1). A) Using the convolution formula, find the pdf ??(?) of the random variable ?=?+?, and graph it. B) What is the moment generating function of ??

Let A ∈ L(U, V ) and B ∈ L(V, W). Assume that V is finite-dimensional....

Let A ∈ L(U, V ) and B ∈ L(V, W). Assume that V is finite-dimensional. Let X be a 3 × 5 matrix and Y be a 5 × 2 matrix. What are the largest and smallest possible ranks of X, Y, and XY? Give examples of the matrix to support your answers

Let W be a random variable giving the number of heads minus the number of tails...

Let W be a random variable giving the number of heads minus the number of tails in three independent tosses of an unfair coin where p = P(H) = 1 3 , and q = P(T) = 2 3 . (a) List the elements of the sample space S for the three tosses of the coin and to each sample point assign a value of W. (b) Find P(−1 ≤ W < 1). (c) Draw a graph of the probability...

Let X ∈ L(U, V ) and Y ∈ L(V, W). You may assume that V...

Let X ∈ L(U, V ) and Y ∈ L(V, W). You may assume that V is finite-dimensional. 1)Prove that dim(range Y) ≤ min(dim V, dim W). Explain the corresponding result for matrices in terms of rank 2) If dim(range Y) = dim V, what can you conclude of Y? Give some explanation 3) If dim(range Y) = dim W, what can you conclude of Y? Give some explanation

Construct NFA of following languages and convert it to equivalent DFA. The set of all binary...

Construct NFA of following languages and convert it to equivalent DFA. The set of all binary strings such that 3th symbol from right end is 0.

Subjects