Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet {a, b} defined inductively as follows: • Base case: the empty word λ and the word a belong to S • Inductive rule: if ω is a string of S then both ω b and ω b a belong to S as well. 1. Prove that if a string ω belongs to S, then ω does not have two or more consecutive a’s. 2. Prove that for any n ≥ 0, if ω is a string of length n over the alphabet {a, b} that does not have two or more consecutive a’s, then ω is a string of S.

Expert Solution

Please hit the like button if you find this answer to be helpful. Thank you!

Colby Messinger answered 2 years ago

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x,...

Draw PDA transition diagram for the following language: The set of strings over the alphabet {x, y} where 2 * (# of x's) = 3 * (#y's) That is, if we let nx be the number of x's and ny be the number of y's, then the strings in these language are those where 2nx = 3ny Try to find a PDA that is as simple and elegant as possible (do not convert from CFG). ------------------------------------------------------------------------------------------------------------------ USE Notation between transition:...

Java programming problem: For simplicity, you can consider DNA sequences as strings in the alphabet of...

Java programming problem: For simplicity, you can consider DNA sequences as strings in the alphabet of {A, C, G, T}. Implement a special hash table to store all short DNA segments of certain length (e.g., 20) found in a long DNA sequence. Every DNA segment is stored as a (key, value) pair, where the key is the sequence of the segment, and the value is the position of the segment in the DNA. For example given a DNA sequence of...

Using the pigeonhole theorem prove that any set of 220 10-character strings over the alphabet {a,b,c,d}...

Using the pigeonhole theorem prove that any set of 220 10-character strings over the alphabet {a,b,c,d} contains a pair of anagrams.

(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0,...

(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0, 1}.

Recognizing partitions - sets of strings. (b) Let A be the set of words in the...

Recognizing partitions - sets of strings. (b) Let A be the set of words in the Oxford English Dictionary (OED). For each positive integer j, define Aj to be the set of all words with j letters in the OED. For example, the word "discrete" is an element of A8 because the word "discrete" has 8 letters. The longest word in the OED is "pneumonoultramicroscopicsilicovolcanoconiosis" which has 45 letters. You can assume that for any integer i in the range...

4. Consider bit strings with length l and weight k (so strings of l 0’s and...

4. Consider bit strings with length l and weight k (so strings of l 0’s and 1’s, including k 1’s). We know how to count the number of these for a ﬁxed l and k. Now, we will count the number of strings for which the sum of the length and the weight is ﬁxed. For example, let’s count all the bit strings for which l + k = 11. (a) Find examples of these strings of diﬀerent lengths. What...

For simplicity, you can consider DNA sequences as strings in the alphabet of {A, C, G,...

For simplicity, you can consider DNA sequences as strings in the alphabet of {A, C, G, T}. Implement a special hash table to store all short DNA segments of certain length (e.g., 20) found in a long DNA sequence. Every DNA segment is stored as a (key, value) pair, where the key is the sequence of the segment, and the value is the position of the segment in the DNA. For example given a DNA sequence of ACGTACGTTT, there are...

Consider a consumer maximizing his preferences over a budget set (which is defined by a weak...

Consider a consumer maximizing his preferences over a budget set (which is defined by a weak inequality involving prices and income). Which of the following assumptions on preferences guarantees that a bundle lying in the interior of the budget set is not a maximizer? (A) Transitivity (B) Convexity (C) Continuity (D) Monotonicity (E) Homotheticity

The subset-sum problem is defined as follows. Given a set of n positive integers, S =...

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3, ..., an} and positive integer W, is there a subset of S whose elements sum to W? Design a dynamic program to solve the problem. (Hint: uses a 2-dimensional Boolean array X, with n rows and W+1 columns, i.e., X[i, j] = 1,1 <= i <= n, 0 <= j <= W, if and only if there is a subset of...

Let L be the set of all languages over alphabet {0}. Show that L is uncountable,...

Let L be the set of all languages over alphabet {0}. Show that L is uncountable, using a proof by diagonalization.

Question