Let L1 be the language of the binary representations of all positive integers divisible by 4....

Let L1 be the language of the binary representations of all positive integers divisible by 4. Let L2 be the language of the binary representations of all positive integers not divisible by 4. None of the elements of these languages have leading zeroes.

a) Write a regular expression denoting L1.

b) Write a regular expression denoting L2.

c) a) Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L1. This state diagram should be complete: it should handle all strings of 0’s and 1’s.

d) Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L2. This state diagram should be complete: it should handle all strings of 0’s and 1’s.

Expert Solution

Colby Messinger answered 2 years ago

Consider all positive integers less than 100. Find the number of integers divisible by 3 or...

Consider all positive integers less than 100. Find the number of integers divisible by 3 or 5? Consider strings formed from the 26 English letters. How many strings are there of length 5? How many ways are there to arrange the letters `a',`b', `c', `d', and `e' such that `a' is not immediately followed by`e' (no repeats since it is an arrangement)?

Let E be the set of all positive integers. Define m to be an "even prime"...

Let E be the set of all positive integers. Define m to be an "even prime" if m is even but not factorable into two even numbers. Prove that some elements of E are not uniquely representable as products of "even primes." Please be as detailed as possible!

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...

3. (4 marks) Let a and b be positive integers. Is gcd(5a + b, 11a +...

3. Let a and b be positive integers. Is gcd(5a + b, 11a + 2b) = gcd(2a + b, 3a + 2b)? If yes provide a proof. If not, provide a counterexample.

Prove the following. Let T denote the integers divisible by three. Find a bijection f :...

Prove the following. Let T denote the integers divisible by three. Find a bijection f : Z→T (Z denotes all integers).

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose...

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose sum is 2n − 2. Prove that there exists a tree T on n vertices whose vertices have degrees a1, a2, . . . , an. Sketch of solution: Prove that there exist i and j such that ai = 1 and aj ≥ 2. Remove ai, subtract 1 from aj and induct on n.

Consider the group Z/mZ ⊕ Z/nZ, for any positive integers m and n that are divisible...

Consider the group Z/mZ ⊕ Z/nZ, for any positive integers m and n that are divisible by 4. How many elements of order 4 does G have, and why?

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Question#1 How many positive integers between 100 and 888 inclusive, a) are divisible by 7? b)...

Question#1 How many positive integers between 100 and 888 inclusive, a) are divisible by 7? b) are odd? c) have distinct digits? d) are not divisible by 6? e) are divisible by either 4 or 7? f) are not divisible by either 4 or 7? g) are divisible by 4 but not by 7? h) are divisible by 4 and 7? Question#1 How many positive integers between 100 and 888 inclusive, a) are divisible by 7? b) are odd? c)...

Question

Let L1 be the language of the binary representations of all positive integers divisible by 4....

Solutions

Expert Solution

Related Solutions

Consider all positive integers less than 100. Find the number of integers divisible by 3 or...

Let E be the set of all positive integers. Define m to be an "even prime"...

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....

3. (4 marks) Let a and b be positive integers. Is gcd(5a + b, 11a +...

Prove the following. Let T denote the integers divisible by three. Find a bijection f :...

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose...

Consider the group Z/mZ ⊕ Z/nZ, for any positive integers m and n that are divisible...

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Question#1 How many positive integers between 100 and 888 inclusive, a) are divisible by 7? b)...