GATE CS Theory of Computation questions

If $L$ and $\overline{L}$ are recursively enumerable then $L$ is

Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free

Which of the following is true for the language $$\left\{ a^p \mid p \text{ is a prime } \right \}?$$

Consider the following Finite State Automaton: The minimum state automaton equivalent to the above FSA has the following number of states:

Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression

The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:

Which of the following languages is regular?

A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has

Which of the following is TRUE?

Which of the following problems is undecidable?

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s ($e.g. $d (101) = 5 ).$ Let $$L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$$Which one of the following statements is true?

If $s$ is a string over $(0+1)^*$ then let $n_0(s)$ denote the number of $0$’s in $s$ and $n_1(s)$ the number of $1$’s in $s$. Which one of the following languages is not regular?

Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\}$. Which of these languages are NOT context free?

The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is TRUE?

Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$? Which one of the following is TRUE?

Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{\#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{\#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE?

Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?