GATE CS Theory of Computation questions

Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$ Which of the languages are regular?

Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have?

Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least

Which of the following statements is true?

Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct?

Consider the following decision problems: $(P1):$ Does a given finite state machine accept a given string? $(P2):$ Does a given context free grammar generate an infinite number of strings? Which of the following statements is true?

What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states?

Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true?

Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$. Which of the following is TRUE?

If $L1$ is context free language and $L2$ is a regular language which of the following is/are false?

Context-free languages are closed under:

Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?

Which of the following statements is false?

Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is

The string $1101$ does not belong to the set represented by

Regarding the power of recognition of languages, which of the following statements is false?

Which of the following set can be recognized by a Deterministic Finite state Automaton?

If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is true?

Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? Note: $w^R$ is the string obtained by reversing $'w'$.