# Recent questions and answers in Theory of Computation

1 vote
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
2
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
3
Which of the following statements is false? Every context –sensitive language is recursive The set of all languages that are not recursively enumerable is countable The family of recursively enumerable languages is closed under union The families of recursively enumerable and recursive languages are closed under reversal
4
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$
5
Consider the languages: $L_1 = \left\{ww^R \mid w \in \{0, 1\}^* \right\}$ $L_2 = \left\{w\text{#}w^R \mid w \in \{0, 1\}^* \right\}$, where $\text{#}$ is a special symbol $L_3 = \left\{ww \mid w \in \{0, 1\}^* \right\}$ Which one of the following is TRUE? $L_1$ is a deterministic CFL $L_2$ is a deterministic CFL $L_3$ is a CFL, but not a deterministic CFL $L_3$ is a deterministic CFL
6
An instruction pipeline consists of following 5 stages: IF = Instruction Fetch, ID = Instruction Decode, EX = Execute, MA = Memory Access and WB = Register Write Back Now consider the following code: Assume that each stage takes 1 clock cycle for all ... cycles are required to execute the code, without operand forwarding over a bypass network ________. Someone please confirm this i am getting 12
7
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
8
what is the grammar generated by the complement of this DFA and what is the type?
9
Consider the following grammar G. Is this regular? S →EF E → a|∈ F → abF|ac
10
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$
11
Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression $b^*ab^*ab^*ab^*$ $(a + b)^*$ $b^*a(a+b)^*$ $b^*ab^*ab^*$
12
A deterministic finite automaton ($\text{DFA}$) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal $\text{DFA}$ which accepts the same languages as $D$?
13
Which the following is FALSE? Complement of a recursive language is recursive. A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine. Complement of a context free language can be recognized by a ... both recursively enumerable then it is recursive. Complement of a non-recursive language can never be recognized by any Turing machine.
14
Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet $\{a,b\}$, such that no string has $3$ consecutive occurrences of the letter $b$.
15
Find nfa's that accept (a) $L ((a + b) a^*) ∩ L (baa^*)$. (b) $L (ab^*a^*) ∩ L (a^*b^*a)$.
16
Consider a CFG with the following productions. $S \to AA \mid B$ $A \to 0A \mid A0 \mid 1$ $B \to 0B00 \mid 1$ $S$ is the start symbol, $A$ and $B$ ... $\{0, 1\}$ containing at least two $0$'s
17
18
Is the family of regular languages closed under infinite intersection?
1 vote
19
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
20
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
21
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
22
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
1 vote
23
Consider statements S1: The language of all TM’s that accept nothing is a Recursive enumerable language. S2:Complement of the language of all TM's that accept nothing is also Recursive enumerable language. Which of the statements are TRUE?
24
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
25
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the read-write head at the beginning of the computation$)?$”$Is this a decidable question$?$0 votes 2 answers 26 Is membership problem for TM decidable or undecidable? 3 votes 6 answers 27 Minimum number of states required in DFA accepting binary strings not ending in$”101”$is$3456$0 votes 1 answer 28 Let L = (0+1)*1(0+1)^(n−1) and following statements regrading language L: The language L can be recognised by a non-deterministic automaton with (n+1) states. Deterministic automaton recognises this language must have at least 2^n states. (Assume n≥1). Which of the following statement(s) is/ ... -------------- According to me, L can be written as (0+1)*1(0+1)* which makes option D most suitable. 17 votes 2 answers 29 Which of the following languages is (are) non-regular?$L_1 = \{0^m1^n \mid 0 \leq m \leq n \leq 10000\}L_2 = \{w \mid w $reads the same forward and backward$\}L_3 = \{w \in \{0, 1\} ^* \mid w$contains an even number of 0's and an even number of 1's$\}L_2$and$L_3$only$L_1$and$L_2$only$L_3$only$L_2$only 23 votes 7 answers 30 Consider the regular expression$R = (a + b)^* \ (aa + bb) \ (a + b)^*$Which one of the regular expressions given below defines the same language as defined by the regular expression$R$?$(a(ba)^* + b(ab)^*)(a + b)^+(a(ba)^* + b(ab)^*)^*(a + b)^*(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$31 votes 7 answers 31 Consider the regular expression$R = (a + b)^* (aa + bb) (a + b)^*$Which deterministic finite automaton accepts the language represented by the regular expression$R$? 33 votes 3 answers 32 Consider the regular expression$R = (a + b)^* (aa + bb) (a + b)^*$Which of the following non-deterministic finite automata recognizes the language defined by the regular expression$R$? Edges labeled$\lambda $denote transitions on the empty string. 42 votes 10 answers 33 The regular expression$0^*(10^*)^*$denotes the same set as$(1^*0)^*1^*0+(0+10)^*(0+1)^*10(0+1)^*$None of the above 1 vote 3 answers 34 0 votes 2 answers 35 1 vote 5 answers 36 A pushdown automata behave like a Turing machine when number of auxiliary memory is: (1) 0 (2) 1 (3) 1 or more (4) 2 or more 4 votes 5 answers 37 Let us define an operation$truncate$, which removes the rightmost symbol from any string. For example,$truncate (aaaba)$is$aaab$. The operation can be extended to languages by$truncate (L)= ${$truncate(w):w ∈ L$} Show how, given a dfa for any regular language L, ...$truncate (L)$. From this, prove that if$L$is a regular language not containing$λ$, then$truncate (L)$is also regular. 0 votes 5 answers 38 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 47 votes 7 answers 39 Let$L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e.,$L$is the set of all the bit strings with even numbers of$1$s. Which one of the regular expressions below represents$L$?$(0^*10^*1)^*0^*(10^*10^*)^*0^*(10^*1)^*0^*0^*1(10^*1)^*10^*\$