Q1: Consider the following sets: (2019)
S1: Set of all recursively enumerable languages over the alphabet {0, 1}.
S2: Set of all syntactically valid C programs.
S3: Set of all languages over the alphabet {0, 1}.
S4: Set of all non-regular languages over the alphabet {0, 1}.
Which of the above sets are uncountable?
(a) S1 and S2
(b) S3 and S4
(c) S2 and 53
(d) S1 and S4
Ans: (b)
Sol:
Every TM can be encoded with 0's and 1's, it means that every TM can be represented by a unique binary number.
Let ∑ = {0, 1} then set of all binary strings = ∑*. We know that, ∑* is countable Set of all TM's is countable.
S1: Set of all recursively enumerable languages over the alphabet {0,1}
Every Recursively enumerable language have a TM, and set of all TM's is countable. Therefore, set of all
Recursively enumerable languages is countable.
S2: Set of all syntactically valid C programs. We can make a one to one equivalence for all valid C programs
and all valid TM encodings. Since, the set of all valid TM encodings is countable, it means that the set of all
syntactically valid C programs is also countable.
Therefore Set of all syntactically valid C programs are countable.
S3: Set of all languages over the alphabet {0, 1}. It is 2∑* which is uncountable as the power set of an infinite
set is uncountable.
S4: Set of all non-regular languages over the alphabet {0, 1}
We know that, set of all languages is uncountable and set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as union of two countable sets cannot make an uncountable set.
Answer is B.
Q2: Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L (M) be the language accepted by a Turning machine M. Which of the following decision problems are undecidable? (2017 SET-2)
I. Given a regular expression R and a string w, is WEL(R)? (d)
II. Given a context-free grammar G, L(G) = ϕ?
III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?
IV. Given a Turning machine M and a string w, is W ∈ L(M)?
(a) I and IV only
(b) II and III only
(c) II, III and IV only
(d) III and IV only
Ans: (d)
Sol:
1st statement is Membership problem of regular language = decidable
2nd statement is Emptyness problem of CFL = decidable
3rd statement is accept everthing problem of CFL = undecidable
4th statement is Membership problem of RE language = undecidable
D is answer.
Q3: Which of the following decision problems are undecidable? (2016 SET-1)
I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = ϕ?
II. Given a CFG G = (N,S,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = ϕ?
(a) I and IV only
(b) II and III only
(c) III and IV only
(d) II and IV only
Ans: (c)
Sol:
I. is Decidable, we may use cross product of NFA (or by converting them into DFA), if We didn't get final states of both together at any state in it. then L(N1) ∩ L(N2) = ϕ, Disjoint languages.
II. Membership in CFG is Decidable (CYK algorithm)
III. Equivalence of Two context free grammars is Undecidable.
IV. For TM M, L(M) = ϕ is Undecidable.
Correct Answer: C
Q4: Which one of the following problems is undecidable? (2014 SET-3)
(a) Deciding if a given context-free grammar is ambiguous
(b) Deciding if a given string is generated by a given context-free grammar
(c) Deciding if the language generated by a given context-free grammar is empty
(d) Deciding if the language generated by a given context-free grammar is finite.
Ans: (a)
Sol:
Context free grammar is not closed under ambiguity. A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set. Here, context free grammar generates a context free language and set of all context free languages is also a set. But, ambiguity is not an operation and hence we can never say that CFG is closed under ambiguity. Thus, problem mentioned in option (A) is undecidable.
Q5: Let ∑ be a finite non-empty alphabet and let ∑* be the power set of ∑* .
Which one of the following is TRUE? (2014 SET-3)
(a) Both 2∑* and ∑* are countable
(b) 2∑* is countable * is uncountable
(c) 2∑* is uncountable and * is countable
(d) Both 2∑*and ∑* are uncountable
Ans: (c)
Sol:
A set is countable means there exist a enumeration procedure to generate each of its elements and for a given element of set, it take finite step to generate it using the enumeration procedure.
Let ∑ = {a,b} and there exist a enumeration procedure to generate all the string of the language *.
Σ* = {ε, a, b, aa, ab, ba, bb, aaa,…}
Here, enumeration procedure is simply the generating string of the language by length for the fixed length string are in alphabetical order.
This way ∑* is countably infinite & 2∑* will be uncountable set
Because the power set of any countably infinite set is uncountable.
Correct Answer: C
Q6: Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE? (2014 SET-2)
(a) If A ≤m B and B is recursive then A is recursive
(b) If A ≤m B and A is undecidable then B is undecidable
(c) If A ≤m B and B is recursively enumerable then A is recursively enumerable.
(d) If A ≤m B and B is not recursively enumerable then A is not recursively enumerable
Ans: (d)
Sol:
The rules are: If A ≤m B
Rule 1: If B is recursive then A is recursive.
Rule 2: If B is recursively enumerable then A is recursively enumerable.
Rule 3: If A is not recursively enumerable then B is not recursively enumerable.
Rule 4: If A is undecidable then B is undecidable.
Other than these rules, all conclusion are false.
so option (D) is false
Q7: Which of the following is/are undecidable? (2013)
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ* ?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
(a) 3 only
(b) 3 and 4 only
(c) 1, 2 and 3 only
(d) 2 and 3 only
Ans: (d)
Sol:
Correct Option: D
- First is Emptiness for CFG.
- Second is everything for CFG.
- Third is Regularity for REC
- Fourth is equivalence for regular.
Q8: Which of the following problems are decidable? (2012)
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is I also context-free?
3) If L is a regular language, then, is I also regular?
4) If L is a recursive language, then, is L also recursive?
(a) 1, 2, 3, 4
(b) 1, 2
(c) 2, 3, 4
(d) 3, 4
Ans: (d)
Sol:
Lets see the options one by one...
1) is undecidable.. This can be correlated to computability of Turing machine.. Specifically halting property of
Turing Machine which is undecidable..
2) option is also undecidable as complement of context free language may or may not be context free
language..So we cannot say with surety that for the class of context free languages, the complementary
language will also be context free..
3) and 4) are decidable as regular and recursive languages are closed under complementation..
Hence D) should be correct answer..
