# Recent questions tagged theory-of-computation

1
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable undecidable interpretive non-deterministic
2
The defining language for developing a formalism in which language definitions can be stated, is called syntactic meta language decidable language intermediate language high level language
3
Regular expression $(a \mid b)(a \mid b)$ denotes the set $\{a,b,ab,aa\}$ $\{a,b,ba,bb\}$ $\{a,b\}$ $\{aa,ab,ba,bb\}$
4
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
1 vote
5
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
6
A language $L$ for which there exists a $TM\;\;’T’,$ that accepts every word in $L$ and either rejects or loops for every word that is not in $L,$ is said to be Recursive Recursively enumerable NP-HARD None of the above
1 vote
7
The logic of pumping lemma is a good example of the pigeon-hole principle the divide and conquer technique recursion iteration
8
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
9
Choose the correct statements. A total recursive function is also a partial recursive function A partial recursive function is also a total recursive function A partial recursive function is also a primitive recursive function None of the above
1 vote
10
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options
11
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options
12
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options
13
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
14
If $L1$ and $L2$ are regular sets then intersection of these two will be : Regular Non Regular Recursive Non Recursive
15
Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$
16
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
1 vote
17
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
18
What is the relation between $DFA$ and $NFA$ on the basis of computational power ? $DFA$ > $NFA$ $NFA$ > $DFA$ Equal Can't be said
1 vote
19
How many DFA's exits with two states over input alphabet $\left \{ 0,1 \right \}$ $16$ $26$ $32$ $64$
1 vote
20
Complement of $\left (a+b \right)^{*}$ will be : $Phi\left ( \Phi \right )$ Null $a$ $b$
21
Finite automata requires minimum ____________ number of stacks. $1$ $0$ $2$ None of the options
22
Which of the following are not regular? Strings of even number of a’s Strings of a’s , whose length is a prime number. Set of all palindromes made up of a’s and b’s. Strings of a’s whose length is a perfect square. (a) and (b) only (a), (b) and (c) only (b),(c) and (d) only (b) and (d) only
1 vote
23
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$? $\{\in \}$ $\{\in,1\}$ $\phi$ $1^{\ast}$
1 vote
24
Given the following statements: A class of languages that is closed under union and complementation has to be closed under intersection A class of languages that is closed under union and intersection has to be closed under complementation Which of the following options is correct? Both (a) and (b) are false Both (a) and (b) are true (a) is true, (b) is false (a) is false, (b) is true
25
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$
26
Given the following two languages : $L_{1}= \{a^{n}b^{n}, \mid n\geq 0,n \neq 100 \}$ $L_{2}= \{w \in \{a,b,c \} ^{\ast} \mid n_{a}(w)=n_{b}(w)=n_{c}(w) \}$ Which of the following options is correct? Both $L_{1}$ and $L_{2}$ ... are context free language $L_{1}$ is context free language, $L_{2}$ is not context free language $L_{1}$ is not context free language, $L_{2}$ is context free language
27
Which of the following pairs have different expressive power? Single-tape-turing machine and multi-dimensional turing machine. Multi-tape turing machine and multi-dimensional turing machine. Deterministic push down automata and non-deterministic pushdown automata. Deterministic finite automata and Non-deterministic finite automata
Which of the following strings would match the regular expression : $p+ [3-5] * [xyz]$? $p443y$ $p6y$ $3xyz$ $p35z$ $p353535x$ $ppp5$ I, IlI and VI only IV, V and VI only II, IV and V only I, IV and V only
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$