Recent questions tagged iitb-ms-phd-test-dec

In this question, DFA refers to a deterministic finite-state automaton, and NFA refers to a non-deterministic finite-state automaton. Consider the regular language $\left...

A student wishes to build circuits representing propositional logic formulas. However, she doesn't have the usual "$\mathrm{AND}$", "$\mathrm{OR}$", "$\mathrm{NOT}$" gate...

Consider the alphabet $\Sigma=\{a, b, c, d\}$. Let $S_{n}$ be the number of $n$-length strings in $\Sigma^{*}$, which have an even number of $a^{\prime}$ s. Answer the fo...

Consider the following languages:$L_{1}=\left\{0^{p} 1^{q} \mid q=(p \% 4)\right.$ and $q$ is a prime number $\}$$L_{2}=\left\{0^{p} 1^{q} \mid p=(q \% 4)\right.$ and $q$...

Let $\Sigma$ be a finite alphabet of size $n \geq 2$ and $a, b \in \Sigma$ such that $a \neq b$. Consider the language $L=\Sigma^{*} a b \Sigma^{*}$ over $\Sigma$. Define...

Consider the grammar below with start symbol $S$.\[\begin{array}{l}S \rightarrow A B S \quad \mid \quad A B \\A \rightarrow a A \quad \mid \quad a \\B \rightarrow b A\end...

In this question, $\varphi, \psi$ represent propositional logic formulas. Wherever we say "equivalent", we mean logically equivalent, i.e. their truth tables are identica...

Let $p$ and $q$ be two propositional variables. Consider formulae $\phi_{1}, \phi_{2}$ defined over variables $p, q$ (and contains no other variables) such that the truth...

Consider the following bubble sort algorithm, where $A$ is the input array (with distinct elements) and $n$ is the length of the array. The function call to $\operatornam...