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}$:
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.
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?
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.
@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 ?
Languages over alphabet set are uncountable so, answer should be (E).
@gabbar i think they r talking abt 2Σ*
I too think same.
∑1={a}.So set of finite length word is {a}*.
Now Language over ∑1 is just 2{a}*....so it is uncountable.
Same for L2 too.
Please correct me if i m wrong
This might help! https://gateoverflow.in/2235/gate1997-3-4
https://gateoverflow.in/278095/countable-set
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.
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
∑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