menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

TIFR2015-B-8

23 votes
2.1k views

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.
in Theory of Computation
edited by 2.1k views
12

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.

0

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?

2
Strings in language are finite, i.e. no string is of infinite length but language can have infinite strings.
0

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

@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 ?

0
set of languages over any no of alphabet are uncountable .

5 Answers

15 votes
 
Best answer

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


edited by
0
countably infinite means?
–1
strings that can be generated from a language

eg:(a+b)* epsilon,a,b,aa,ab,ba,bb....so on
0
How I'm not getting..
1
need more clarity,will anyone explain in details ?

why shouldn't they be countably infinite
0

@gabbar i think they r talking abt 2Σ*

11

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

0
yes it is right
1
0
0
your answer is wrong.Set of all string over any finite alphabet are countable.
2

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.

5 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


reshown by
1 vote

∑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 

0 votes
Answer should e)

edited by
–6 votes
(B) will be answer

We can draw DFA for both of them. But DFA always contain a loop
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

26 votes
3 answers
1
1.9k views
TIFR2015-A-8
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.9k views
20 votes
2 answers
2
1.2k views
TIFR2015-B-10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the following is true? ... regular. $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the following is true? $L_{1}$ ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
asked Dec 8, 2015 in Theory of Computation makhdoom ghaya 1.2k views
18 votes
4 answers
3
1k views
TIFR2015-B-7
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)^{*}a = a(ba + a)^{*}$ None of the above.
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)^{*}a = a(ba + a)^{*}$ None of the above.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1k views
13 votes
3 answers
4
1k views
TIFR2015-B-6
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic finite state ... but not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic finite state automaton ... but not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...