Let = {a, b}. Define FINITE to be the set of all finite languages over ,...

Transcribed Image Text:

Let = {a, b}. Define FINITE to be the set of all finite languages over Σ, and let COFINITE = {LLE FINITE} (where, for any language L over Σ, Ī is the complement of L, that is, Σ* \ L). For example, Σ* is in coFINITE because its complement is Ø, which is finite. (Please think carefully about this definition, and note that coFINITE isn't the same thing as FINITE.) (a) Are there any languages over Σ in FINITE coFINITE? Prove your answer. (b) Are there any languages over Σ that are not in FINITEUCOFINITE? Prove your answer. Let = {a, b}. Define FINITE to be the set of all finite languages over Σ, and let COFINITE = {LLE FINITE} (where, for any language L over Σ, Ī is the complement of L, that is, Σ* \ L). For example, Σ* is in coFINITE because its complement is Ø, which is finite. (Please think carefully about this definition, and note that coFINITE isn't the same thing as FINITE.) (a) Are there any languages over Σ in FINITE coFINITE? Prove your answer. (b) Are there any languages over Σ that are not in FINITEUCOFINITE? Prove your answer.

Answer rating: 100% (QA)

a Yes there are languages over that are in both FINITE and coFINITE This is because a language Lis i... View the full answer