Question 1 |

Consider the following sets:

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?

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?

S1 and S2 | |

S3 and S4 | |

S2 and S3 | |

S1 and S4 |

Question 1 Explanation:

Question 2 |

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 ?

I. Given a regular expression R and a string w, is w\in L(R)?

II. Given a context-free grammar G, L(G)=\phi?

III. Given a context-free grammar G, is L(G)=\Sigma* for some alphabet \Sigma?

IV. Given a Turning machine M and a string w, is w\inL(M)?

I. Given a regular expression R and a string w, is w\in L(R)?

II. Given a context-free grammar G, L(G)=\phi?

III. Given a context-free grammar G, is L(G)=\Sigma* for some alphabet \Sigma?

IV. Given a Turning machine M and a string w, is w\inL(M)?

I and IV only | |

II and III only | |

II, III and IV only | |

III and IV only |

Question 2 Explanation:

Question 3 |

Which of the following decision problems are undecidable?

I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi?

II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)?

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

IV. Given a TM M, is L(M) = \phi?

I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi?

II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)?

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

IV. Given a TM M, is L(M) = \phi?

I and IV only | |

II and III only | |

III and IV only | |

II and IV only |

Question 3 Explanation:

Question 4 |

Which one of the following problems is undecidable?

Deciding if a given context-free grammar is ambiguous | |

Deciding if a given string is generated by a given context-free grammar | |

Deciding if the language generated by a given context-free grammar is empty | |

Deciding if the language generated by a given context-free grammar is finite. |

Question 4 Explanation:

Question 5 |

Let \Sigma be a finite non-empty alphabet and let 2^{\Sigma^{*}} be the power set of \Sigma^{*} . Which one of the following is TRUE?

Both 2^{\Sigma^{*}} and \Sigma^{*} are countable | |

2^{\Sigma^{*}} is countable \Sigma^{*} is uncountable | |

2^{\Sigma^{*}} is uncountable and \Sigma^{*} is countable | |

Both 2^{\Sigma^{*}} and \Sigma^{*} are uncountable |

Question 5 Explanation:

Question 6 |

Let A \leq _{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?

If A\leq _{m}B and B is recursive then A is recursive | |

If A\leq _{m}B and A is undecidable then B is undecidable | |

If A\leq _{m}B and B is recursively enumerable then A is recursively enumerable. | |

If A\leq _{m}B and B is not recursively enumerable then A is not recursively enumerable |

Question 6 Explanation:

Question 7 |

Which of the following is/are undecidable?

1. G is a CFG. Is L(G) = \Phi?

2. G is a CFG. Is L(G) = \Sigma ^{*} ?

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

1. G is a CFG. Is L(G) = \Phi?

2. G is a CFG. Is L(G) = \Sigma ^{*} ?

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

3 only | |

3 and 4 only | |

1, 2 and 3 only | |

2 and 3 only |

Question 7 Explanation:

Question 8 |

Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is a context-free language, then, is \bar{L} also context-free?

3) If L is a regular language, then, is \bar{L} also regular?

4) If L is a recursive language, then, is \bar{L} also recursive?

1) Does a given program ever produce an output?

2) If L is a context-free language, then, is \bar{L} also context-free?

3) If L is a regular language, then, is \bar{L} also regular?

4) If L is a recursive language, then, is \bar{L} also recursive?

1, 2, 3, 4 | |

1,2 | |

2,3,4 | |

3,4 |

Question 8 Explanation:

Question 9 |

Which of the following are decidable?

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

I. Whether the intersection of two regular languages is infinite

II. Whether a given context-free language is regular

III. Whether two push-down automata accept the same language

IV. Whether a given grammar is context-free

I and II | |

I and IV | |

II and III | |

II and IV |

Question 9 Explanation:

Question 10 |

Which of the following problems is undecidable?

Membership problem for CFGs. | |

Ambiguity problem for CFGs. | |

Finiteness problem for FSAs. | |

Equivalence problem for FSAs. |

Question 10 Explanation:

There are 10 questions to complete.