GATE CS Theory of Computation questions

Consider the following two regular expressions over the alphabet $\{0,1\}$ : $r= 0^{*}+1^{*}$ $s = 01^{*} + 10^{*}$ The total number of strings of length less than or equal to $5$, which are neither in $r$ nor in $s$, is ________.

​​​​Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?

​​Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$?

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ and $L_{2}=\left\{w \in(a+b)^{*}|| w \mid \leq 4\right\}$, where $|w|$ denotes the length of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.

Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following regular expressions correctly describes the language accepted by …

Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions: …

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

Consider the context-free grammar $G$ below $$\begin{array}{l} S \rightarrow a S b \mid X \\ X \rightarrow a X \mid X b \mid a \mid b, \end{array}$$ where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$. Which one of the following statements is $\text{CORRECT}?$

Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$, labelled $c / X / \gamma$, where $c$ is an input symbol or $\epsilon, X$ is a stack symbol, …

Consider the language $L$ over the alphabet $\{0,1\}$, given below: $$L=\left\{w \in\{0,1\}^{*} \mid w \text{ does not contain three or more consecutive } 1 \text{ 's }\right\} .$$ The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

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

Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$

Which of the following is/are undecidable?

Consider the following languages: $L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$ $L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$ Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are $\text{TRUE}?$

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?

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?

Consider the following language: $$L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$$ Which one of the following deterministic finite automata accepts $L?$

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages. $$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L_2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$$ Which one of the …

In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $$(q,Y) \in \delta(p,a,X).$$Consider the following pushdown automaton over the input alphabet $\Sigma = \{a,b\}$ and stack alphabet …