GATE CS Regular and Context-free Languages questions

Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages. Which of the following statements is/are always true?

Consider the following context-free grammar $G$. $$\begin{array}{l} S \rightarrow a b a A B A b b a \\ A \rightarrow a a B B A b \mid b B a b a a \\ B \rightarrow a B b \mid a b \end{array}$$ In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols. Let $L(G)$ be the language …

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^{i} b^{j} c^{k} d^{\ell} \mid i, j, k, \ell \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

Consider the following two languages over the alphabet $\{a, b\}$: $$\begin{array}{l} L_{1}=\left\{\alpha \beta \alpha \mid \alpha \in\{a, b\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \\ L_{2}=\left\{\alpha \beta \alpha \mid \alpha \in\{a\}^{+} \text{AND } \beta \in\{a, b\}^{+}\right\} \end{array}$$ Which ONE of the following statements is CORRECT?

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} L_{1} & =\left\{a^{m} b^{m} c^{m+n} \mid m, n \geq 1\right\} \\ L_{2} & =\left\{a^{m} b^{n} c^{m+n} \mid m, n \geq 1\right\} \end{aligned}$$ Which ONE of the following statements is CORRECT?

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{*}$, and $\alpha \in \Sigma$, let $\#_{\alpha}(x)$ denote the number of occurrences of $\alpha$ in $x$. Which one or more of the following option(s) define(s) regular language(s)?

Consider the two lists List I and List II given below: …

​Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

Which of the following statements is/are $\text{CORRECT}?$

Which of the following statements is/are $\text{TRUE}?$

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive?

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct?

Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?

Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE?

Consider the following languages. $$\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$$ Which one of the following is TRUE?

Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

If $L$ is a regular language over $\Sigma = \{a,b\}$, which one of the following languages is NOT regular?

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?