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}$: Both are finite. Both are countably infinite. $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable. Theory of Computation tifr2015 identify-class-language + – makhdoom ghaya asked Dec 7, 2015 • edited May 15, 2018 by Milicevic3306 makhdoom ghaya 4.6k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply srestha commented Aug 6, 2016 reply Follow Share Ans 2) 2 votes 2 votes Rupendra Choudhary commented Dec 2, 2017 reply Follow Share L1 : set of all possible languages over ∑={a} so L1 may be regular,context free, context sensitive , or RE. Individually all languages are CI(countably infinite) but their set (more clearly power set) would be UCI(uncountably infinite) So in the same way set of all languages over {a} or {a,b} (2∑*)would be UCI. 13 votes 13 votes MiNiPanda commented Jun 30, 2018 reply Follow Share A language over an alphabet is a set of finite length words comprising letters of the alphabet. @ Rupendra Choudhary why does the question say words are of "finite" length? 0 votes 0 votes Anu007 commented Jun 30, 2018 reply Follow Share Strings in language are finite, i.e. no string is of infinite length but language can have infinite strings. 3 votes 3 votes MiNiPanda commented Jun 30, 2018 reply Follow Share Anu007 Given input symbols {a,b} and finite length string suppose k we can have only finite comibations of strings right? For eg if k is given as 2 then we can have strings only in {Epsilon,a,b,aa,ab,ba,bb}. We cannot have infinite strings using finite length. Please point out the mistake. 0 votes 0 votes ankitgupta.1729 commented Jan 2, 2019 reply Follow Share @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 ? 1 votes 1 votes Nitesh Singh 2 commented Jan 24, 2019 reply Follow Share set of languages over any no of alphabet are uncountable . 1 votes 1 votes Deepak Poonia commented Sep 25, 2023 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
Best answer 15 votes 15 votes Languages over alphabet set are uncountable so, answer should be (E). Pooja Palod answered Dec 8, 2015 • edited Jun 15, 2018 by Milicevic3306 Pooja Palod comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments srestha commented Dec 15, 2018 reply Follow Share https://gateoverflow.in/278095/countable-set 0 votes 0 votes suraj prasad shaw commented May 11, 2019 reply Follow Share your answer is wrong.Set of all string over any finite alphabet are countable. 0 votes 0 votes mrinmoyh commented Sep 17, 2019 reply Follow Share Let L1 and L2 be the set of languages here L1 & L2 is not a language, they are set of languages. as we know that $\Sigma ^{*}$ is countable, so subset of this is also countable. If it would said that L1 & L2 is language over $\Sigma$ then L1 & L2 are countable. but L1 & L2 are set of all languages possible over $\Sigma$. i.e they are $2^{\Sigma ^{*}}$ which is uncountable. 3 votes 3 votes Please log in or register to add a comment.
7 votes 7 votes Number of strings over a language is countable infinite Number of languages possible is uncountable Similar question:https://gateoverflow.in/2050/gate2014-3_16?show=2050#q2050 admin answered Jan 2, 2016 • reshown Oct 30, 2017 by Arjun admin comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Examples of countably infinite sets are: The set of all squares A U B U C, A = {a1,a2,a3, ….} B = {b1,b2,b3,….}, C = {c1,c2,c3…} N x N sh!va answered Aug 6, 2016 sh!va comment Share Follow See all 0 reply Please log in or register to add a comment.
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 ShiveshRoy answered Dec 7, 2017 ShiveshRoy comment Share Follow See all 0 reply Please log in or register to add a comment.