search
Log In

Recent questions and answers in Theory of Computation

1 vote
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
answered 2 days ago in Theory of Computation wafer 174 views
0 votes
2 answers
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
answered 3 days ago in Theory of Computation Pallav98 74 views
0 votes
1 answer
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
answered 3 days ago in Theory of Computation Pallav98 38 views
0 votes
7 answers
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$
answered 3 days ago in Theory of Computation Lakshman Patel RJIT 125 views
26 votes
4 answers
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
answered 4 days ago in Theory of Computation Mitali gupta 2.2k views
2 votes
1 answer
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
answered 5 days ago in Theory of Computation sachin486 235 views
58 votes
7 answers
7
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
answered 5 days ago in Theory of Computation Duy Le 8.7k views
0 votes
6 answers
8
what is the grammar generated by the complement of this DFA and what is the type?
answered 5 days ago in Theory of Computation tech_beardo 96 views
33 votes
8 answers
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$
answered Jul 24 in Theory of Computation Asim Siddiqui 4 4.3k views
27 votes
6 answers
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^*$
answered Jul 23 in Theory of Computation Asim Siddiqui 4 3.5k views
23 votes
5 answers
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$?
answered Jul 23 in Theory of Computation Asim Siddiqui 4 2.9k views
20 votes
2 answers
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.
answered Jul 22 in Theory of Computation Srivathsa 2.1k views
23 votes
5 answers
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$.
answered Jul 20 in Theory of Computation Aditi0103 3k views
27 votes
5 answers
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
answered Jul 15 in Theory of Computation prajjwalsingh_11 3.3k views
3 votes
4 answers
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
answered Jul 14 in Theory of Computation kartik.kharbanda 1.9k views
1 vote
1 answer
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?
answered Jul 12 in Theory of Computation Gaurav Yadav 79 views
37 votes
9 answers
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$
answered Jul 8 in Theory of Computation TheAnteamatter 5.8k views
0 votes
1 answer
25
3 votes
6 answers
27
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.
answered Jun 23 in Theory of Computation ninja_hattori 48 views
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
answered Jun 20 in Theory of Computation TheAnteamatter 1.9k views
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)^+$
answered Jun 20 in Theory of Computation TheAnteamatter 4.4k views
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$?
answered Jun 20 in Theory of Computation TheAnteamatter 2.6k views
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.
answered Jun 20 in Theory of Computation TheAnteamatter 3.2k views
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
answered Jun 19 in Theory of Computation Jhaiyam 5.4k views
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
answered Jun 16 in Theory of Computation pritambiswas000007 2.6k views
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.
answered Jun 16 in Theory of Computation roh 805 views
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
answered Jun 15 in Theory of Computation pritambiswas000007 54 views
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^*$
answered Jun 11 in Theory of Computation Tsering_Dorjay 6.8k views
0 votes
2 answers
40
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes.
answered Jun 9 in Theory of Computation Duraikrishnakumar 699 views
To see more, click for all the questions in this category.
...