TIFR CSE 2015 | Part B | Question: 8

Question

Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the set of languages over $\sum_{1}$ and $\sum_{2}$ respectively. Which of the following is true about $L_{1}$ and $L_{2}$:

• A. Both are finite.
• B. Both are countably infinite.
• C. $L_{1}$ is countable but $L_{2}$ is not.
• D. $L_{2}$ is countable but $L_{1}$ is not.
• E. Neither of them is countable.

Comments

@MiNiPanda '$k$' is not fixed. right ? It can be any natural number and set of natural numbers is an infinite set. So, $k$ $\in$ $\mathbb{N}$ by considering  $\mathbb{N}$ starts from $0$ . So, $k$ can take any value from the set of natural number. So, we will get 0 length string , 1 length string, 2 length string, .... . So, here , we are considering each string is of finite length and we can write the enumeration procedure by taking length of each string in increasing order and if some strings have same length then we apply the lexicographical order. So, like this we can write the Enumeration procedure for this set which makes this set to a countable set.

Now, Suppose, We have a set of strings in which each string has infinite length then is it possible to write enumeration procedure for this set by considering one infinity is bigger than other infinity ?

---

set of languages over any no of alphabet are uncountable .

---

Detailed Video Solution: https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=6986s 

For EVERY $\Sigma,$ the set of all languages is uncountable.

The set of all languages over $\Sigma$ is the powerset of $\Sigma^*$ i.e. $P(\Sigma^*).$

Proof:

By Cantor’s theorem, we know: If $S$ is ANY infinite set, then $P(S)$ is always uncountable. (Or we can say, NO infinite powerset is countable.)

Since, for every $\Sigma$, $\Sigma^*$ is infinite, hence, $P(\Sigma^*)$ is uncountable.

Learn Cantor’s Theorem & its Consequences HERE.

Answer 1

Answer should e)

Answer 2

(B) will be answer

We can draw DFA for both of them. But DFA always contain a loop