edited by
4,426 views
25 votes
25 votes

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}$:

  1. Both are finite.
  2. Both are countably infinite.
  3. $L_{1}$ is countable but $L_{2}$ is not.
  4. $L_{2}$ is countable but $L_{1}$ is not.
  5. Neither of them is countable.
edited by

6 Answers

Best answer
15 votes
15 votes

Languages over alphabet set are uncountable so, answer should be (E).

edited by
1 votes
1 votes

Answer must be 2

Finite sets

- finite number of elements

- can be counted Infinite sets - infinite number of elements

Equinumerous sets:

Sets A and B are equinumerous if there is a bijection f : A → B E.G.: A = {1,2,3}, B = {a,b,c}

Countably infinite sets:

A set is countably infinite if it is equinumerous with N (the set of natural numbers)

Sets that are not countable, are called uncountable.

  1. Examples of countably infinite sets are: The set of all squares
  2. A U B U C, A = {a1,a2,a3, ….} B = {b1,b2,b3,….}, C = {c1,c2,c3…}
  3. N x N
1 votes
1 votes

1={a}

L1 is any subset of {a}* i.e. from {a}* any string could be present or absent  which is countably infinite

Hence |L1|= 2{a}*   which is Uncountable

Similarly, L2 is also Uncountable 

Answer:

Related questions

18 votes
18 votes
4 answers
3
makhdoom ghaya asked Dec 7, 2015
2,321 views
Let $a, b, c$ be regular expressions. Which of the following identities is correct?$(a + b)^{*} = a^{*}b^{*}$$a(b + c) = ab + c$$(a + b)^{*} = a^{*} + b^{*}$$(ab + a)^{*}...