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.

Expert Solution

Colby Messinger answered 3 years ago

Given an alphabet Σ, what are the languages L over Σ for which L ∗ is...

Given an alphabet Σ, what are the languages L over Σ for which L ∗ is finite? How many such languages exist?

2. Let S be the set of strings over the alphabet Σ = {a, b, c}...

2. Let S be the set of strings over the alphabet Σ = {a, b, c} defined recursively by (1) λ ∈ S and a ∈ S; and (2) if x ∈ S, then bxc ∈ S. Recall that λ denotes the empty string which has no letters and has length 0. List all strings of S which are length at most seven. 3. Prove the following theorem by induction: For every integer n ≥ 1, 1 · 2 +...

3. Are the following languages A and B over the alphabet Σ = {a, b, c,...

3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonregular? • For a language that is regular, give a regular expression that defines it. • For a nonregular language, using the pumping lemma prove that it is not regular. (a) A = {d 2j+1c k+1 | j ≥ k ≥ 0} · {c r+2b 2s+3 | r ≥ 0 and s ≥ 0} (b) B = {a 2j+2b k+3c j+1...

1. Let a < b. (a) Show that R[a, b] is uncountable

Let X be an uncountable set, let τf be the finite complement topology on X, and...

Let X be an uncountable set, let τf be the finite complement topology on X, and let τc be the countable complement topology; namely, we have τf ={U⊂X : X\U is finite}∪{∅}, τc={U⊂X : X\U is countable}∪{∅}, where “countable” means that the set is either finite or countably infinite (in bijection with the natural numbers). (a) What are the compact subspaces of (X, τf )? Are all compact subspaces closed in (X, τf )? (b) What are the compact subspaces...

(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}.

4. Construct regular expressions for the following languages over the alphabet {a, b}: a. Strings that...

4. Construct regular expressions for the following languages over the alphabet {a, b}: a. Strings that do not begin with an “a”. b. Strings that contain both aa and bb as substrings. 5. Let ? = {? ?? ?? ? | ? > ? + ?}. a. List all strings of length 7. (use power notation: i.e. aabbbbaaaaaaaa is a2b 4a 8 ) b. Use the Pumping Lemma for Regular Languages to prove that L is not regular.

1: Let X be the set of all ordered triples of 0’s and 1’s. Show that...

1: Let X be the set of all ordered triples of 0’s and 1’s. Show that X consists of 8 elements and that a metric d on X can be defined by ∀x,y ∈ X: d(x,y) := Number of places where x and y have different entries. 2: Show that the non-negativity of a metric can be deduced from only Axioms (M2), (M3), and (M4). 3: Let (X,d) be a metric space. Show that another metric D on X can...

1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L...

1. Prove the language L is not regular, over the alphabet Σ = {a, b}. L = { aib2i : i > 0} 2) Prove the language M is not regular, over the alphabet Σ = {a, b}. M = { wwR : w is an element of Σ* i.e. w is any string, and wR means the string w written in reverse}. In other words, language M is even-length palindromes.

show that if I is uncountable,then 2I is not metrizable. hint: Suppose I as index set.

Question