search
Log In

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count}&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline
\end{array}}}$$

Recent questions in Theory of Computation

2 votes
1 answer
1
0 votes
1 answer
2
0 votes
4 answers
3
Let $L$ be a language and $L’$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $L’$ is RE. One of the $L$ and $L’$ is RE but not recursive;the other is not RE. Both $L$ and $L’$ are RE but not recursive. Both $L$ and $L’$ are recursive.
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 103 views
0 votes
3 answers
4
Let $L1$ be a recursive language, and let $L2$ be a recursively enumerable but not recursive language. Which one of the following is TRUE? $L1’$ is recursive and $L2’$is recursively enumerable. $L1’$ is recursive and $L2’$is not recursively enumerable. $L1’$ and $L2’$is recursively enumerable. $L1’$ is recursively enumerable and $L2’$is recursive.
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 88 views
0 votes
7 answers
5
According to the given language, which among the following expressions does it correspond to ? Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$. $(0+1+0+1+0+1+0+1)^4$ $(0+1)^4$ $(01)^4$ $(0+1+\varepsilon)^4$
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 228 views
0 votes
1 answer
6
Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true? Any derivation of $W_1$ has exactly the same number of steps as any derivation of $W_2$. Different derivation have different length. Some derivation of $W_1$ may be shorter than the derivation of $W_2$ None of the options
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 114 views
0 votes
3 answers
7
A regular expression is $(a+b^{\ast}c)$ is equivalent to set of strings with either $a$ or one or more occurrence of $b$ followed by $c$. $(b^{\ast}c+a)$ set of strings with either $a$ or zero or more occurrence of $b$ followed by $c$. Both (B) and (C)
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 201 views
0 votes
2 answers
8
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: Any given CFG is ambiguous or not. ... CFG $G$, to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 287 views
0 votes
4 answers
9
Recursive enumerable languages are not closed under _________. Set difference Complement Both (A) and (B) None of the options
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 108 views
0 votes
5 answers
10
What is the meaning of regular expression $\Sigma^*001\Sigma^*$? Any string containing ‘$1$’ as substring Any string containing ‘$01$’ as substring Any string containing ‘$011$’ as substring All string containing ‘$001$’ as substring
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 146 views
0 votes
2 answers
11
If any string of a language $L$ can be effectively enumerated by an enumerator in a lexicographic order then language $L$ is _______. Regular Context free but not necessarily regular Recursive but not necessarily context free Recursively enumerable but not necessarily recursive
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 110 views
0 votes
4 answers
12
The collection of Turing recognizable languages are closed under: Union Intersection Complement Concatenation Star Closure (i) Only Both (i),(iv) (i),(ii),(iv)and(v) All of the options
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 119 views
0 votes
2 answers
13
0 votes
3 answers
14
Which of the following statement is true? $S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine. $S2$: Every non-deterministic Turing machine has an equivalent deterministic Turing machine. $S1$ $S2$ Both $S1$ and $S2$ None of the options
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 205 views
0 votes
6 answers
15
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 511 views
0 votes
2 answers
16
Which of the following is equivalent regular expressions? $((01)^*(10)^*)^*$ $(10+01)^*$ $(01)^*+(11)^*$ $(0^*+(11)^*+0^*)^*)$ (i) and (ii) (ii) and (iii) (iii) and (iv) (iv) and (i)
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 103 views
0 votes
1 answer
17
0 votes
2 answers
18
Let $n$ is the length of string to test for membership, then the number of table entry in CYK algorithm is $n(n+1)$ $n^2+1$ $n^2-1$ $n(n+1)/2$
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 141 views
0 votes
5 answers
19
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 106 views
0 votes
2 answers
20
...