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?

Expert Solution

If Σ is an alphabet, and L ⊆ Σ∗, then L is a (formal) language over Σ.
Language: A (possibly infinite) set of strings all of which are chosen from some
Σ∗
A language over Σ need not include strings with all symbols of Σ
Thus, a language over Σ is also a language over any alphabet that is a superset
of Σ
Examples:

Programming language C
Legal programs are a subset of the possible strings that can be formed from the alphabet of the language (a subset of ASCII characters)
English or French
The language of all strings consisting of
n 0s followed by n 1s (n≥0): {ǫ, 01, 0011, 000111, . . .}
The set of strings of 0s and 1s with an equal number of each:{ǫ, 01, 10, 0011, 0101, 1001, . . .}
Σ∗ is a language for any alphabet Σ
∅, the empty language, is a language over any alphabet
{ǫ}, the language consisting of only the empty string, is also a language over any alphabet
{w | w consists of an equal number of 0 and 1}

venereology answered 2 hours ago

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

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.

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.

Automata Question. Over the alphabet Σ = {a, b}: 1) Give a DFA, M1, that accepts...

Automata Question. Over the alphabet Σ = {a, b}: 1) Give a DFA, M1, that accepts a Language L1 = { w | w has exactly 2 a’s } 2) Give a DFA, M2, that accepts a Language L2 = { w | w has at least 2 b’s } 3) Give acceptor for L1 intersection L2 4) Give acceptor for L1 - L2

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules...

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules for L1 are as follows: S → TT S → U T → 0T T → T0 T→ 1 U → 0U00 U → 1 Q → λ P → QU Transform this grammar into Chomsky Normal Form, consistent with the CNF specification in the Quick Reference, and using only Variables { S, T, U, V, W, X }. Implement that CNF grammar in...

Describe the languages specified by the following regular expressions: 1. \\(_+)/ 2. (\(740\)...-...)|(...-...) (The alphabet is...

Describe the languages specified by the following regular expressions: 1. \\(_+)/ 2. (\(740\)...-...)|(...-...) (The alphabet is {1,2,3,4,5,6,7,8,9,0})

Theory of computation: Consider the alphanumeric alphabet Σ = {a, b, . . . , z,...

Theory of computation: Consider the alphanumeric alphabet Σ = {a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9} and let L be the language of all regular expressions over Σ: L = {w ∈ Σ ∪ {∅,(,), ∪, ·, * }* | w is a syntactically legal regular expression over Σ} Give an unambiguous context-free grammar that generates L. The grammar should use the following precedence levels, from...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines Y...

Are the following languages over {a, b} regular? If they are then prove it. If they...

Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma a) {ap | p is a prime number} b) {xax | x Î{a,b}*} (start by listing some strings in, not in, the language

Question