menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Recent questions and answers in Theory of Computation

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions and answers in Theory of Computation

1 vote
2 answers
1
monotonically increasing grammar
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
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
UGCNET-Jan2017-III: 62
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 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
UGCNET-Jan2017-III: 63
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
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
NIELIT 2017 DEC Scientist B - Section B: 2
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$
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
GATE2005-57
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
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
COA-PIPELINE
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 ... are required to execute the code, without operand forwarding over a bypass network ________. Someone please confirm this i am getting 12
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
GATE2006-34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
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
Doubt-DFA
what is the grammar generated by the complement of this DFA and what is the type?
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
GATE2008-52
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$
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
GATE2007-74
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^*$
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
GATE2011-45
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$?
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
TIFR2014-B-14
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 ... enumerable then it is recursive. Complement of a non-recursive language can never be recognized by any Turing machine.
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
GATE1993-27
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$.
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
GATE2008-IT-34
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
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
GATE2020-CS-10
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
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
Recursive Enumerable Language
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?
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
GATE2015-2-35
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$ ... $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
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
Peter Linz Edition 5 Exercise 12.1 Question 6 (Page No. 308)
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$?$
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$?$
answered Jul 7 in Theory of Computation roh 76 views
3 votes
6 answers
27
ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
answered Jun 28 in Theory of Computation akash18tripathi 716 views
0 votes
1 answer
28
Geekforgeeks full length
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 ... ---------- According to me, L can be written as (0+1)*1(0+1)* which makes option D most suitable.
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
GATE2008-IT-35
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
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
GATE2007-IT-73
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)^+$
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
GATE2007-IT-72
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which deterministic finite automaton accepts the language represented by the regular expression $R$?
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
GATE2007-IT-71
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.
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
GATE2003-14
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
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
ugc net 2018-33
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
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
Peter Linz Edition 4 Exercise 2.1 Question 24 (Page No. 49)
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, ... From this, prove that if $L$ is a regular language not containing $λ$, then $truncate (L)$ is also regular.
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
NIELIT 2017 DEC Scientist B - Section B: 56
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
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
GATE2010-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^*$
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
net 2016 july exam
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.
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.
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...