Computer Science And Engineering - Theory of Computation / FLAT PYQ

Q1.MCQ

Consider the following two languages over the alphabet $\{a, b\}$: $L1 = \{ \alpha \beta \alpha \mid \alpha \in \{a, b\}^+ \text{ AND } \beta \in \{a, b\}^+ \}$ $L2 = \{ \alpha \beta \alpha \mid \alpha \in \{a\}^+ \text{ AND } \beta \in \{a, b\}^+ \}$ Which ONE of the following statements is CORRECT?

Q2.MCQ

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $L1 = \{a^m b^m c^{m+n} \mid m, n \geq 1\}$ $L2 = \{a^m b^n c^{m+n} \mid m, n \geq 1\}$ Which ONE of the following statements is CORRECT?

Q3.MCQ

Consider the following context-free grammar $G$, where $S$, $A$, and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the rules of $G$ are described as: $$S \rightarrow aaB \mid Abb$$ $$A \rightarrow a \mid aA$$ $$B \rightarrow b \mid bB$$ Which ONE of the languages $L(G)$ is accepted by $G$?

Q4.M-MCQ

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$. Identify which of the following language(s) is/are accepted by the given DFA. !image(https://uadmin.udsfgecw.tech/file/download/public/public:2734ea50-83f6-41ef-b8bf-b3a84d0c3788.jpg)

Q5.M-MCQ

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?

Q6.NUMERICAL

Let 𝑆 be the set of all ternary strings defined over the alphabet {𝑎, 𝑏, 𝑐}. Consider all strings in 𝑆 that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is . (Answer in integer)

Q7.MCQ

Consider the following grammar $G$, with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3). $$S \rightarrow daT \mid \underline{\quad (1) \quad}$$ $$T \rightarrow aS \mid bT \mid \underline{\quad (2) \quad}$$ $$R \rightarrow \underline{\quad (3) \quad} \mid \epsilon$$ The set of terminals is $\{a, b, c, d, f\}$. The FIRST and FOLLOW sets of the different non-terminals are as follows. $$\text{FIRST}(S) = \{c, d, f\}, \text{FIRST}(T) = \{a, b, \epsilon\}, \text{FIRST}(R) = \{c, \epsilon\}$$ $$\text{FOLLOW}(S) = \text{FOLLOW}(T) = \{c, f, \$\}, \text{FOLLOW}(R) = \{f\}$$ Which one of the following options CORRECTLY fills in the incomplete productions?

Q8.M-MCQ

Consider the 5-state DFA $M$ accepting the language $L(M) \subset (0 + 1)^$ shown below. For any string $w \in (0 + 1)^$, let $n0(w)$ be the number of $0$'s in $w$ and $n1(w)$ be the number of $1$'s in $w$. image needed to be inserted here Which of the following statements is/are FALSE?

Q9.NUMERICAL

Let $G = (V, \Sigma, S, P)$ be a context-free grammar in Chomsky Normal Form with $\Sigma = \{a, b, c\}$ and $V$ containing $10$ variable symbols including the start symbol $S$. The string $w = a^{30}b^{30}c^{30}$ is derivable from $S$. The number of steps (application of rules) in the derivation $S \to^ w$ is

Q10.NUMERICAL

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