Question

In: Computer Science

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.

  1. If any number is not divisible by 4 and leaves 1 as a remainder the control will move on to state q1.
  2. 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.
  3. If any number is not divisible by 4 and leaves 3 as remainder the control moves to q3.
  4. 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 1 year 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.
L= {w belongs to {0,1}* | the number of 0's is a prime number} . Prove...
L= {w belongs to {0,1}* | the number of 0's is a prime number} . Prove that the language L is not regular.
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}
Lab 2 ∑={0,1} L = {w : if |w| is odd w begins with 11}. List...
Lab 2 ∑={0,1} L = {w : if |w| is odd w begins with 11}. List the indistinguishability classes for L(M). Include the following information for each class c, where wc is a string in c: • A short description or characteristic function that describes the strings in c. • Whether wc is or is not in L(M). • ∀z(wcz ∈ L(M) iff … ). This rule must be different for each equivalence class — that is what makes them...
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...
Create a DFA for L = {wwR|w ∈ {0, 1}∗}. WR represents the reverse of the...
Create a DFA for L = {wwR|w ∈ {0, 1}∗}. WR represents the reverse of the string. Explain your answer.
(10) Let L = { <D> | D is a DFA that accepts sR whenever it...
(10) Let L = { <D> | D is a DFA that accepts sR whenever it accepts s } . Show that L is Turing-decidable.
Draw a DFA for the following ( ∑ = {0,1}):                                 Set of all strings with.
Draw a DFA for the following ( ∑ = {0,1}):                                 Set of all strings with at most one consecutive pair of 1’s.
Draw DFA C = { w is an element of {a,b}* and #a(w) is even and...
Draw DFA C = { w is an element of {a,b}* and #a(w) is even and #b(w) us a multiple of 3)
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.
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT