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

3 votes
2 answers
1
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
asked Jul 20 in Theory of Computation Sanjay Sharma 217 views
1 vote
1 answer
2
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet $\{a,b\}$? $a^*b^*$ $(a\mid b)^*$ $(ab)^+$ $(a\mid b^*)$
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 224 views
1 vote
1 answer
3
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to deterministic push-down ... are equivalent to deterministic push-down automata. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 144 views
1 vote
1 answer
4
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language? $L_1L_2$ $L_1\cap L_2$ $L_1\cap R$ $L_1\cup L_2$
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 123 views
1 vote
1 answer
5
If $L$ be a language recognizable by a finite automaton, then language from $\{L\} = \{w$ such that $w$ is a prefix of $v$ where $v\in L\}$, is a regular language. context-free language. context-sensitive language. recursive enumeration language
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 118 views
0 votes
1 answer
6
Which of the following statements is correct? $A=\{a^nb^n\mid n= 0,1,2,3\dots \}$ is regular language Set $B$ of all strings of equal number of $a$'s and $b$'s defines a regular language $L(A^*B^*) \cap B$ gives the set $A$ None of these.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 106 views
0 votes
1 answer
7
1 vote
1 answer
8
Palindromes can't be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half. All of the above.
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 288 views
1 vote
1 answer
9
If $L1$ is CFL and $L2$ is regular language which of the following is false? $L1-L2$ is not Context free $L1$ intersection $L2$ is Context free $\sim L1$ is Context free Both (A) and (C)
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 89 views
0 votes
2 answers
10
Which of the following is wrong? Turing machine is a simple mathematical model of general purpose computer Turing machine is more powerful than finite automata Turing Machine can be simulated by a general purpose computer All of these
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 312 views
0 votes
1 answer
11
Given two DFA's $M1$ and $M2$. They are equivalent if $M1$ and $M2$ has the same number of states $M1$ and $M2$ accepts the same language i.e $L(M1)=L(M2)$ $M1$ and $M2$ has the same number of final states None of the above
asked Mar 31 in Theory of Computation Lakshman Patel RJIT 92 views
0 votes
1 answer
12
0 votes
4 answers
13
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 71 views
0 votes
3 answers
14
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 58 views
0 votes
7 answers
15
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 156 views
0 votes
1 answer
16
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 84 views
0 votes
3 answers
17
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 128 views
0 votes
2 answers
18
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 198 views
0 votes
4 answers
19
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 75 views
0 votes
5 answers
20
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 94 views
...