Search results for gate+theory-of-computation / GATE Overflow for GATE CSE

4 votes

1 answer

21

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

1 votes

0 answers

22

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

3 votes

3 answers

23

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

2 votes

3 answers

24

Virtual Gate Test Series: Theory Of Computation - Regular Languages
The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$ Note$:-$ $aba ∈ L $since $'aba'$ contains $1$ occurrence of $'ab'$ and $1$ occurrence of $'ba'$ but $ abab ∉ L$

The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$Note$:-$ $aba ∈ L $since $'a...

smartmeet

4.3k views

smartmeet asked Dec 8, 2016

0 votes

1 answer

25

Virtual Gate Test Series: Theory Of Computation - Languages
Answe is B, but why is L2 not regular? How to solve it? For L2, $ y=x^{1/n}$ I am not understanding why is this not right?

Answe is B, but why is L2 not regular? How to solve it? For L2, $ y=x^{1/n}$ I am not understanding why is this not right?

Purple

447 views

Purple asked Jan 12, 2017

0 votes

0 answers

26

User GATE 2006
Let L1={0n+m1n0m∣n,m≥0}L1={0n+m1n0m∣n,m≥0}, L2={0^n+m 1^n+m 0^m∣n,m≥0}L2={0^n+m 1^n+m 0^m∣n,m≥0} and L3={0^n+m 1^n+m 0^n+m∣n,m≥0}L3={0^n+m 1^n+m 0^n+m∣n,m≥0}. Which of these languages are NOT context free? L1 only L3 only L1 and L2 L2 and L3 THE ABOVE LANGUAGE HAS EPLSILON SO ITS NOT RECOGONIZED BY ANY TURING MACHINE HENCE IS IT NOT RECURSIVELY ENUMERABLE??

LetL1={0n+m1n0m∣n,m≥0}L1={0n+m1n0m∣n,m≥0},L2={0^n+m 1^n+m 0^m∣n,m≥0}L2={0^n+m 1^n+m 0^m∣n,m≥0} andL3={0^n+m 1^n+m 0^n+m∣n,m≥0}L3={0^n+m 1^n+m 0^n+m∣...

Venkat Sai

259 views

Venkat Sai asked Oct 3, 2017

16 votes

1 answer

27

GATE CSE 2009 | Question: 14
Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE? There is no polynomial time algorithm for $\pi_A$. If $\pi_A$ can be solved deterministically in polynomial time, then P = NP. If $\pi_A$ is NP-hard, then it is NP-complete. $\pi_A$ may be undecidable.

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?There is no polynomial time algorithm for $\pi_A$.If $\pi_A$ can be solved ...

Kathleen

9.7k views

Kathleen asked Sep 22, 2014

25 votes

1 answer

28

GATE CSE 2013 | Question: 18
Which of the following statements are TRUE? The problem of determining whether there exists a cycle in an undirected graph is in $P$. The problem of determining whether there exists a cycle in an undirected graph is in $NP$. If a problem A is $NP-Complete$, there exists a non-deterministic ... solve $A$ $1$, $2$ and $3$ $1$ and $2$ only $2$ and $3$ only $1$ and $3$ only

Which of the following statements are TRUE?The problem of determining whether there exists a cycle in an undirected graph is in $P$.The problem of determining whether the...

Arjun

7.5k views

Arjun asked Sep 23, 2014

1 votes

1 answer

29

Virtual Gate Test Series: Theory Of Computation - Regular Languages
Which one of the following languages over the alphabet ${0, 1}$ is regular$?$ $(A)$ The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively $(B)$ The language of palindromes, i.e., bit strings $x$ ... The kleene closure $L^{*},$ where $L$ is the language in $(C)$ above Ans is $D$ please explain$?$

Which one of the following languages over the alphabet ${0, 1}$ is regular$?$$(A)$ The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively$...

indrajeet

924 views

indrajeet asked Feb 5, 2017

0 votes

1 answer

30

Virtual Gate Test Series: Theory Of Computation - Languages
For $A,B\subseteq \Sigma ^{*},$ define $A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$ If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$ Regular CFL but not Regular Recursive but not CFL None of the above

For $A,B\subseteq \Sigma ^{*},$ define$A/B=\{x\in\Sigma^{*}\mid \exists y\in B,xy\in A\}$If $L$ is a $\text{CFL}$ and $R$ is $\text{Regular},$ then $L/R$ is$?$RegularCFL ...

smartmeet

791 views

smartmeet asked Jan 12, 2017

0 votes

1 answer

31

Virtual Gate Test Series: Theory Of Computation - CFL Self Concatenation
Let $L$ be a given context-free language over the alphabet $\{a, b\}$ then $L_{2} = L·L$ is $\text{CFL.}$ Is $\text{CFL.}$ in general closed under $\text{self-concatenation?}$ If $L={ a^nb^n }$ then $L.L= { a^nb^na^nb^n }$ $\text{(or)}$ $L.L= { a^nb^na^mb^m } ?$

Let $L$ be a given context-free language over the alphabet $\{a, b\}$ then $L_{2} = L·L$ is $\text{CFL.}$Is $\text{CFL.}$ in general closed under $\text{self-concatenat...

yg92

509 views

yg92 asked Jan 25, 2017

2 votes

2 answers

32

Virtual Gate Test Series: Theory Of Computation - DFA
Number of states in the $\text{DFA}$ accepting the language $L=\{a^{n}b^{n}|1\leq n\leq 3\}$ over $\sum=\{a,b\}.$

Number of states in the $\text{DFA}$ accepting the language $L=\{a^{n}b^{n}|1\leq n\leq 3\}$ over $\sum=\{a,b\}.$

Jason GATE

594 views

Jason GATE asked Jan 8, 2017

18 votes

1 answer

33

GATE CSE 2005 | Question: 58
Consider the following two problems on undirected graphs: $\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$? $\beta$: Given $G(V, E)$, does $G$ have an independent set of size $5$ ... $\beta$ is in P Both $\alpha$ and $\beta$ are NP-complete Both $\alpha$ and $\beta$ are in P

Consider the following two problems on undirected graphs:$\alpha$: Given $G(V, E)$, does $G$ have an independent set of size |V| - $4$?$\beta$: Given $G(V, E)$, does $G$ ...

Kathleen

6.6k views

Kathleen asked Sep 22, 2014

0 votes

0 answers

34

Virtual Gate Test Series: Theory Of Computation - Context Sensitive Grammar
How can L(G) be regular? If we derive bSb --> bAcAb, now we have Ab-->b but we do not have the production bA since G is all production except last. So there is no production for A or bA. How can we go further?

How can L(G) be regular?If we derive bSb bAcAb, now we have Ab >b but we do not have the production bA since G is all production except last. So there is no production ...

Purple

433 views

Purple asked Jan 12, 2017

1 votes

1 answer

35

Calicut Gate Academy Test Series
The Java language is: A context free language A context sensitive language A regular language Parsable fully only by a Turing machine

The Java language is:A context free languageA context sensitive languageA regular languageParsable fully only by a Turing machine

PEKKA

325 views

PEKKA asked Dec 5, 2016

3 votes

0 answers

36

GATE CSE 1990 | Question: 15b
Complete the following production rules which generate the language:$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$ where variables $R$ and $Q$ ... $Q \rightarrow R'c$ $cR' \rightarrow ...$ $bR' \rightarrow ...$ $aR' \rightarrow a...$

Complete the following production rules which generate the language:$$L= \left\{a^{n} b^{n} c^{n}\mid a, b, c \in \Sigma \right\}$$ where variables $R$ and $Q$ are used t...

makhdoom ghaya

717 views

makhdoom ghaya asked Nov 26, 2016

1 votes

1 answer

37

Calicut Gate Academy Test Series | TOC Q32
Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}. Then L is Recursively enumerable Not Recursively enumerable Recursive Udecidable (Multiple Options May be Correct . Mark them All )

Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}.Then L isRecursivel...

PEKKA

624 views

PEKKA asked Dec 5, 2016

0 votes

1 answer

38

Calicut Gate Academy Test Series | TOC
L={ambnckdl | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is best fit under which language class RL DCFL CFL CSL

L={ambnckdl | (n-k ) is odd only if (m-l) is odd , m,n,k,l >=0 } is best fit under which language classRLDCFLCFLCSL

PEKKA

343 views

PEKKA asked Dec 5, 2016

1 votes

2 answers

39

Virtual Gate Test Series: Theory Of Computation - Turing Machine
Consider the following two decision problems Whether a Turing machine takes more than $481$ steps on input $\epsilon?$ Whether a Turing machine accepts the null string $\epsilon?$ Which of the following statements is true$?$ ... undecidable but $B$ is decidable Both $A$ and $B$ are decidable Both $A$ and $B$ are undecidable

Consider the following two decision problemsWhether a Turing machine takes more than $481$ steps on input $\epsilon?$Whether a Turing machine accepts the null string $\ep...

Hradesh patel

514 views

Hradesh patel asked Oct 7, 2016

1 votes

1 answer

40

Virtual Gate Test Series: Theory Of Computation - Regular Languages

Hradesh patel

361 views

Hradesh patel asked Oct 6, 2016

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