Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for gate+theory-of-computation
0
votes
0
answers
1
Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
raj_uddeshya157
83
views
raj_uddeshya157
asked
Dec 27, 2023
Theory of Computation
theory-of-computation
gate-preparation
dcfl
dpda
npda
context-free-language
+
–
0
votes
1
answer
2
Test Series: Is null string considered as a proper prefix of any string? According to me, total number of proper prefixes for n length string should be (n-1), can anyone please get this point cleared.
tishhaagrawal
314
views
tishhaagrawal
asked
Nov 26, 2023
Theory of Computation
test-series
theory-of-computation
gate-preparation
general-topic-doubt
+
–
0
votes
1
answer
3
#syallabus completion
HELLO SIR , SIR I HAVE LEFT WITH TOC, CD , DM AND CN AND I THOUGHT , I SHOULD LEAVE ANY TWO OF THESE SO THAT I CAN FOCUS ON REVISION PROPERLY… SO , I WANT TO KNOW THAT WHICH 2 OF THESE SHOULD LEFT ASIDE .
HELLO SIR , SIR I HAVE LEFT WITH TOC, CD , DM AND CN AND I THOUGHT , I SHOULD LEAVE ANY TWO OF THESE SO THAT I CAN FOCUS ON REVISION PROPERLY… SO , I WANT TO KNOW THAT ...
jaswinder
228
views
jaswinder
asked
Oct 12, 2023
GATE
out-of-gate-syllabus
discrete-mathematics
theory-of-computation
computer-networks
compiler-design
goclasses
+
–
0
votes
0
answers
4
TOC unacademy
Consider the following equation: L1:{TM IT M accepts Є} L2:{TM IT M accepts only Є} Which of the following is not semidecidable? SELECT ONE OPTION A L1 only B L2 only C Both L1 and L2 D none of the above
Consider the following equation: L1:{TM IT M accepts Є} L2:{TM IT M accepts only Є} Which of the following is not semidecidable? SELECT ONE OPTION A L1 onlyB L2 onlyC B...
AyanDutta
277
views
AyanDutta
asked
May 8, 2023
Theory of Computation
theory-of-computation
non-gate
+
–
2
votes
0
answers
5
gate academy
I think S1 is false because, for n=0, no 0’s will be added in stack, but in the transition to the next state (q2->q3) there is one mandatory 1 canceling out 0 in stack which will be absent in case of n=0. But solutions say S1 is true.
I think S1 is false because, for n=0, no 0’s will be added in stack, but in the transition to the next state (q2->q3) there is one mandatory 1 canceling out 0 in stack...
h4kr
334
views
h4kr
asked
Nov 20, 2022
Theory of Computation
theory-of-computation
dpda
virtual-gate-test-series
+
–
36
votes
3
answers
6
GATE IT 2007 | Question: 18
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections ... be that of A combinational circuit A finite automaton A pushdown automaton with one stack A pushdown automaton with two stacks
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow extern...
Ishrat Jahan
6.5k
views
Ishrat Jahan
asked
Oct 29, 2014
Computer Networks
gateit-2007
computer-networks
theory-of-computation
normal
network-security
out-of-gate-syllabus
+
–
0
votes
1
answer
7
NIELIT 2016 MAR Scientist C - Section C: 15
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
The defining language for developing a formalism in which language definitions can be stated, is calledsyntactic meta languagedecidable languageintermediate languagehigh ...
admin
678
views
admin
asked
Apr 2, 2020
Theory of Computation
nielit2016mar-scientistc
theory-of-computation
identify-class-language
non-gate
+
–
2
votes
1
answer
8
Virtual Gate Test Series: Theory Of Computation - Finite Automata
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything? answer is 20 or 64?
How many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with alphabet a and b, that accepts everything?answer is 20 o...
aditi19
1.9k
views
aditi19
asked
Mar 24, 2019
Theory of Computation
theory-of-computation
finite-automata
virtual-gate-test-series
+
–
1
votes
2
answers
9
Virtual Gate Test Series: Theory Of Computation - Languages
If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of $x$ is a square } \Bigr \}$ then $L$ is Regular Recursive but not context free Context Free but not regular None of the above
If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of $x$ is a square } \Bigr \}$ then $L$ isRegularRecursive but not context freeContext Free but not regula...
aditi19
644
views
aditi19
asked
Mar 24, 2019
Theory of Computation
theory-of-computation
identify-class-language
virtual-gate-test-series
+
–
0
votes
0
answers
10
Virtual GATE
Let A be a regular set. Consider the two sets below L1={x | $\exists n\geq 0, \exists y\epsilon A :$ y=$x^n$} L2={x | $\exists n\geq 0, \exists y\epsilon A :$ x=$y^n$} which of the following statements is true? L1 and L2 both are regular L1 is regular but L2 is not L1 is not regular but L2 is L1 and L2 both are non-regular
Let A be a regular set. Consider the two sets belowL1={x | $\exists n\geq 0, \exists y\epsilon A :$ y=$x^n$}L2={x | $\exists n\geq 0, \exists y\epsilon A :$ x=$y^n$}which...
aditi19
523
views
aditi19
asked
Mar 17, 2019
Theory of Computation
virtual-gate
test-series
theory-of-computation
regular-language
regular-expression
+
–
1
votes
1
answer
11
Virtual Gate Test Series: Theory Of Computation - Languages
Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language: L := {xy | x, y ∈ Σ* , na(x) = nb(y)} What can we say about L? L is regular, but not context-free. L is context-free, but not regular. L is Σ*. None of these.
Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language:L := {xy ...
jatin khachane 1
356
views
jatin khachane 1
asked
Jan 26, 2019
Theory of Computation
theory-of-computation
identify-class-language
virtual-gate-test-series
+
–
23
votes
4
answers
12
GATE CSE 2012 | Question: 4
Assuming $\textsf{P} \neq \textsf{NP}$, which of the following is TRUE? $\textsf{NP-complete} = \textsf{NP}$ $\textsf{NP-complete} \cap \textsf{P} = \phi$ $\textsf{NP-hard} = \textsf{NP}$ $\textsf{P} = \textsf{NP-complete}$
Assuming $\textsf{P} \neq \textsf{NP}$, which of the following is TRUE?$\textsf{NP-complete} = \textsf{NP}$$\textsf{NP-complete} \cap \textsf{P} = \phi$$\textsf{NP-hard} ...
gatecse
9.0k
views
gatecse
asked
Aug 5, 2014
Theory of Computation
gatecse-2012
theory-of-computation
p-np-npc-nph
non-gate
+
–
1
votes
0
answers
13
Virtual Gate Test Series: Theory Of Computation - Finite Automata
For a binary string, $x = a_0,a_1, · · · ,a_n−1$ define $val(x)$ to be the value of x interpreted as a binary number, where $a_0$ is the most significant bit. More formally, $val(x)$ ... a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either $4$ or $ 5?$
For a binary string, $x = a_0,a_1, · · · ,a_n−1$ define $val(x)$ to be the value of x interpreted as a binary number, where $a_0$ is the most significant bit. More f...
Gupta731
564
views
Gupta731
asked
Dec 26, 2018
Theory of Computation
theory-of-computation
finite-automata
virtual-gate-test-series
+
–
9
votes
3
answers
14
Virtual Gate Test Series: Theory Of Computation - Regular Languages
Let A be a regular set . Consider the two sets below: L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$} L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =y^{n}$} Which of the following is True ? L1 and L2 are Regular L1 is Regular but Not L2 L2 is Regular but Not L1 Both are not Regular
Let A be a regular set . Consider the two sets below:L1 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : y =x^{n}$}L2 = {$x \mid \exists{n}\geq 0 , \exists{y} \in A : x =...
Amit Pal
3.4k
views
Amit Pal
asked
Oct 24, 2016
Theory of Computation
theory-of-computation
regular-language
identify-class-language
virtual-gate-test-series
+
–
8
votes
2
answers
15
GATE CSE 2006 | Question: 31
Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? Both DHAM$_3$ ... NP-hard, but DHAM$_3$ is not DHAM$_3$ is NP-hard, but SHAM$_3$ is not Neither DHAM$_3$ nor SHAM$_3$ is NP-hard
Let SHAM$_3$ be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$ with $|V|$ divisible by $3$ and DHAM$_3$ be the problem of determining if a Hamiltonian...
Rucha Shelke
4.7k
views
Rucha Shelke
asked
Sep 18, 2014
Theory of Computation
gatecse-2006
theory-of-computation
p-np-npc-nph
normal
non-gate
+
–
13
votes
4
answers
16
VirtualGate Test Series: Theory Of Computation - Regular Languages
Consider the following subsets of $\left\{a, b, \$ \right\}^*$ $A=\left\{xy\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$ $ ... are true? $A$ and $B$ both are regular $A$ is regular but $B$ is not $A$ is not regular but $B$ is regular Both are non-regular
Consider the following subsets of $\left\{a, b, \$ \right\}^*$$A=\left\{xy\, |\, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$$B=\left\{x\$y\, |\, x,y\in\left\{a,b\r...
shreshtha5
1.7k
views
shreshtha5
asked
Dec 5, 2015
Theory of Computation
theory-of-computation
regular-language
virtual-gate-test-series
+
–
4
votes
2
answers
17
Virtual Gate Test Series: Theory Of Computation - Languages
Let $L$ be a given context-free language over the alphabet $\{a, b\}$. Construct $L1, L2$ as follows. Let $L1 = L − \{xyx \mid x, y \in \{a, b\}^*\}$, and $L2 = L·L$. Then, Both $L1$ and $L2$ are regular ... $L1$ is regular and $L2$ is context-free. $L1$ and $L2$ both may not be context-free.
Let $L$ be a given context-free language over the alphabet $\{a, b\}$. Construct $L1, L2$ as follows.Let $L1 = L − \{xyx \mid x, y \in \{a, b\}^*\}$,and $L2 = L·L$. Th...
Utsav09
584
views
Utsav09
asked
Jan 27, 2018
Theory of Computation
theory-of-computation
identify-class-language
virtual-gate-test-series
+
–
4
votes
1
answer
18
TIFR CSE 2018 | Part B | Question: 15
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages. $\text{SCYCLE}=\{(G,k)\mid G \text{ contains a cycle of length at most k}\}$ ... $\text{SCYCLE}$ to $\text{LCYCLE}$).
$G$ respresents an undirected graph and a cycle refers to a simple cycle (no repeated edges or vertices). Define the following two languages.$\text{SCYCLE}=\{(G,k)\mid G ...
Arjun
1.0k
views
Arjun
asked
Dec 10, 2017
Theory of Computation
tifr2018
theory-of-computation
reduction
p-np-npc-nph
non-gate
+
–
1
votes
0
answers
19
Virtual Gate Test Series: Theory Of Computation - Homomorphic Image
If $h$ represents the Homomorphic image of a string and $h^{-1}$ represent the Inverse Homomorphic image of a string. We have a language $L$, $(A)\ h(h^{-1}(L)) = L$ ... Some reference given here, but I am not able to understand: https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec08.pdf (5th page)
If $h$ represents the Homomorphic image of a string and $h^{-1}$ represent the Inverse Homomorphic image of a string. We have a language $L$, $(A)\ h(h^{-1}(L)) = L$$(B...
Rishabh Gupta 2
329
views
Rishabh Gupta 2
asked
Jan 27, 2018
Theory of Computation
theory-of-computation
homomorphism
virtual-gate-test-series
+
–
3
votes
3
answers
20
Virtual Gate Test Series: Theory Of Computation - Languages
Consider the following context-sensitive productions $\\S\rightarrow bSb\, |\, AcA \\Ab\rightarrow A,\, Ab\rightarrow b \\bA\rightarrow b,\, bA\rightarrow A$ Let $G$ be grammar given by all the rules except the last, and let $G'$ be the ... is regular Both $L(G)$ and $L(G')$ are regular None of $L(G)$ and $L(G')$ are regular
Consider the following context-sensitive productions$\\S\rightarrow bSb\, |\, AcA \\Ab\rightarrow A,\, Ab\rightarrow b \\bA\rightarrow b,\, bA\rightarrow A$Let $G$ be gra...
shreshtha5
685
views
shreshtha5
asked
Dec 5, 2015
Theory of Computation
theory-of-computation
identify-class-language
virtual-gate-test-series
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register