GATE CS Theory of Computation questions

Which one of the following is not decidable?

Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?

Given $\Sigma=\{a,b\}$, which one of the following sets is not countable?

If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?

Which of the following statements is false?

Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$. Which of the following is true?

Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string). $(00)^ * (\varepsilon +0)$ $(00)^*$ $0^*$ $0(00)^*$

Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\}$ then the languages $L \cup R$ and $R$ are respectively

Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$

In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

Which of the following conversions is not possible (algorithmically)?

Which of the following three statements are true? Prove your answer.

In which of the cases stated below is the following statement true? "For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language".

Which of the following regular expression identities is/are TRUE?

Context-free languages are:

Which of the following is the strongest correct statement about a finite language over some finite alphabet $\Sigma?$

Let $r=1(1+0)^*, s=11^*0 \text{ and } t=1^*0$ be three regular expressions. Which one of the following is true?

Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:

It is undecidable whether:

Recursive languages are: