# Recent posts in 2016

1
Yes you need to study P, NP computational problems
2
Answer is (B) $NP-complete \cap P = \phi$ Since, $P \neq NP$, there is at least one problem in $NP$, which is harder than all $P$ problems. Lets take the hardest such problem, say $X$. Since, $P \neq NP, X \notin P$ . Now, by definition, $NP-complete$ problems ... other $NP-complete$ problem as $hard$ as $X$. So, since $X \notin P$, none of the other $NP-complete$ problems also cannot be in $P$.
3
(C) Every relation in BCNF is also in 3NF. Straight from definition of BCNF.
4
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
5
Consider the following languages $L_1$ = $\{a^nb^n\mid n \ge 0\}$ $L_2$ = Complement($L_1$) Chose the appropriate option regarding the languages $L_1$ and $L_2$ (A) $L_1$ and $L_2$ are context free (B) $L_1$ is context free but $L_2$ is regular (C) $L_1$ is context free and $L_2$ is context sensitive (D) None of the above
6
We can get a DFA for $L = \{x \mid xx &#8714; A\}$ as follows: Take DFA for $A$ $\left(Q, \delta, \Sigma, S, F\right)$ with everything same except initially making $F = \phi$. Now for each state $D \in Q$, consider 2 separate DFAs, one with $S$ as the start state and $D$ as the final ... . But if we make $L$ from $A$ as per (d), it'll be $L = \{a^nb^nc^n \mid n \ge 0\}$ which is not context free..
7
www.gatecse.in and www.gateoverflow.in are two websites that provide extensive information for most of the GATE CSE queries - Almost complete coverage all the required information one needs to know about GATE, right from preparations to the admissions.
While getting information of what GATE is all about, www.gatecse.in played an important role in getting me acquainted with the know-hows of preparation, the standard books and lectures available, and also a lot of statistics from previous year(GATE 2014,2015) results.
When my preparation was at the crucial stage in the last two months, www.gateoverflow.in played the role of helping me get over some of my...
8
Let $Σ = \{a, b, c\}$. Which of the following statements is true? For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx \mid x ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x \mid xx ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx \mid x ∊ A\}$ For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x \mid xx ∊ A\}$
To see more, click for the full list of questions or popular tags.