Recent activity by Silpa / GATE Overflow for GATE CSE

8 answers

1

TIFR CSE 2012 | Part B | Question: 15
Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$ ... . For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.

Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be ...

3.9k views

recategorized Jul 3, 2017

2 answers

2

TIFR CSE 2011 | Part B | Question: 38
Consider the class of recursive and iterative programs. Which of the following is false? Recursive programs are more powerful than iterative programs. For every iterative program there is an equivalent recursive program. ... memory management. Recursive programs do not terminate sometimes. Iterative programs and recursive programs are equally expressive.

Consider the class of recursive and iterative programs. Which of the following is false?Recursive programs are more powerful than iterative programs.For every iterative p...

6.4k views

recategorized Jul 3, 2017

7 answers

3

GATE CSE 2014 Set 2 | Question: 37
Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ be the number of such longest common subsequences between $A$ and $B$. Then $x +10y=$ ___.

Consider two strings $A$="qpqrr" and $B$="pqprqrp". Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ and let $y$ b...

17.0k views

retagged Jul 3, 2017

2 answers

4

GATE CSE 2012 | Question: 5
The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is $\Theta(n\log n)$ $\Theta(n2^n)$ $\Theta(n)$ $\Theta(\log n)$

The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is$\Theta(n\log n)$$\Theta(n2^n)$$\Theta(n)$$\Theta(\log n)$

13.5k views

recategorized Jul 3, 2017

2 answers

5

GATE CSE 2007 | Question: 31
Which of the following languages is regular? $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$ $\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$ $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$ $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$

Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$$\left\{wxw^R \mid x, w \in \{0, 1\}...

14.2k views

retagged Jul 1, 2017

5 answers

6

ISI2014-PCB-CS-4b
Consider the following statement: $\text{ For all languages }L \subseteq \{0, 1\}^*, \text{ if }L^* \text{ is regular then L is regular.}$ Is the above statement true? Justify your answer.

Consider the following statement:$\text{ For all languages }L \subseteq \{0, 1\}^*, \text{ if }L^* \text{ is regular then L is regular.}$Is the above statement true? Just...

1.9k views

retagged Jul 1, 2017

1 answer

7

GATE IT 2006 | Question: 30
Which of the following statements about regular languages is NOT true ? Every language has a regular superset Every language has a regular subset Every subset of a regular language is regular Every subset of a finite language is regular

Which of the following statements about regular languages is NOT true ?Every language has a regular supersetEvery language has a regular subsetEvery subset of a regular l...

8.0k views

retagged Jul 1, 2017

4 answers

8

ISI2015-PCB-CS-5a
Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular. Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 \cup L_2$ is regular.

Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular.Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 ...

1.8k views

retagged Jul 1, 2017

2 answers

9

CMI2010-B-04c
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers. If a language $L$ is accepted by an NFA with $n$ states then there is a DFA with no more than $2^n$ states accepting $L$.

Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.If a language $L$ is accepted by an NFA with $n$ sta...

1.1k views

retagged Jul 1, 2017

3 answers

10

GATE CSE 2007 | Question: 7
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular

Which of the following is TRUE?Every subset of a regular set is regularEvery finite subset of a non-regular set is regularThe union of two non-regular sets is not regular...

15.4k views

retagged Jul 1, 2017

3 answers

11

CMI2015-A-09
Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true: If $L_2$ is regular, then $L_1$ must also be regular. If $L_1$ is regular, then $L_2$ must also be regular. Either both $L_1$ and $L_2$ are regular, or both are not regular. None of the above.

Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true:If $L_2$ is regular, then $L_1$ must also be regu...

1.2k views

edited Jul 1, 2017

3 answers

12

CMI2012-A-01
Let $L \subseteq \{0,1\}^*$. Which of the following is true? If $L$ is regular, all subsets of $L$ are regular. If all proper subsets of $L$ are regular, then $L$ is regular. If all finite subsets of $L$ are regular, then $L$ is regular. If a proper subset of $L$ is not regular, then $L$ is not regular.

Let $L \subseteq \{0,1\}^*$. Which of the following is true?If $L$ is regular, all subsets of $L$ are regular.If all proper subsets of $L$ are regular, then $L$ is regula...

5.8k views

edited Jul 1, 2017

2 answers

13

TIFR CSE 2015 | Part B | Question: 10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.

Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wed...

3.0k views

edited Jul 1, 2017

3 answers

14

GATE CSE 2014 Set 2 | Question: 15
If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language $L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$ Which one of the following is CORRECT? Only I Only II Both I and II Neither I nor II

If $L_1\:=\{a^n \mid n\:\geq\:0\}$ and $L_2\:= \{b^n \mid n\:\geq\:0\}$ , consider $L_1.L_2$ is a regular language$L_1.L_2 = \{a^nb^n \mid n\: \geq \:0\}$Which one of th...

10.8k views

edited Jul 1, 2017

2 answers

15

GATE CSE 2008 | Question: 53
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only

Which of the following are regular sets?$\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$$\left\{a^nb^m \mid n =2m \right\}$$\left\{a^nb^m \mid n \neq m \right\}$$\lef...

9.6k views

edited Jul 1, 2017

2 answers

16

GATE CSE 2001 | Question: 1.4
Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct? Only $S_1$ is correct Only $S_2$ is correct Both $S_1$ and $S_2$ are correct None of $S_1$ and $S_2$ is correct

Consider the following two statements:$S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language$S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \ri...

14.9k views

edited Jul 1, 2017

3 answers

17

GATE CSE 2014 Set 1 | Question: 15
Which one of the following is TRUE? The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular. The language $L$ ... is regular. The language $L = \left\{ww \mid w \in \Sigma^* \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.

Which one of the following is TRUE?The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular.The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is reg...

9.3k views

edited Jul 1, 2017

3 answers

18

GATE CSE 2015 Set 2 | Question: 51
Which of the following is/are regular languages? $L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$ $L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}$ $L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$ $L_1$ and $L_3$ only $L_2$ only $L_2$ and $L_3$ only $L_3$ only

Which of the following is/are regular languages?$L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| 0\right\}, w^R \text{ is the reverse of string } w$$L...

11.2k views

edited Jul 1, 2017

3 answers

19

GATE CSE 2014 Set 1 | Question: 35
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.

Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility?Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)...

8.4k views

edited Jul 1, 2017

7 answers

20

GATE CSE 2016 Set 2 | Question: 44
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$ ... not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive

Consider the following languages.$L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$,$L_{2} = \left\{\left\langl...

33.6k views

retagged Jul 1, 2017

2 answers

21

GATE CSE 2010 | Question: 17
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2 - L_1 \:\text{is recursively enumerable.}$ ... $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$

Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessar...

16.3k views

edited Jul 1, 2017

5 answers

22

GATE IT 2005 | Question: 38
Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state of the PDA. The stack is initialized with one $Z$ before the start of ... $L(P)$ and $N(P)$ are necessarily $Σ^*$. Neither $L(P)$ nor $N(P)$ are necessarily $Σ^*$

Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting ...

12.4k views

edited Jul 1, 2017

2 answers

23

GATE CSE 1996 | Question: 13
Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ ... $\delta(q_2,b,b) = \left\{(q_2, \epsilon)\right\}$ $\delta(q_2,\epsilon,\bot) = \left\{(q_2, \epsilon)\right\}$

Let $Q=\left( \left\{q_1,q_2 \right\}, \left\{a,b\right \}, \left\{a,b,\bot \right\}, \delta, \bot, \phi \right)$ be a pushdown automaton accepting by empty stack for the...

5.7k views

retagged Jul 1, 2017

3 answers

24

GATE IT 2006 | Question: 31
Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?$\{a^nb^nc^n \mid n ≥ 0\}$$\{a^lb^mc^n \mid ...

18.1k views

edited Jul 1, 2017

1 answer

25

GATE CSE 1999 | Question: 1.6
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true? $L_1 = L_2$ $L_1 \supset L_2$ $L_1 \subset L_2$ None

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?$L_1 = L...

22.1k views

retagged Jul 1, 2017

2 answers

26

GATE CSE 1999 | Question: 1.4
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above

Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression cont...

25.2k views

edited Jul 1, 2017

2 answers

27

GATE CSE 1998 | Question: 4
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language: $L=\{w \in \{0, 1\}^* \mid w$ interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:$L=\{w \in \{0, 1\}^* \mid w$ interpreted as binar...

11.8k views

retagged Jul 1, 2017

6 answers

28

GATE CSE 2015 Set 2 | Question: 53
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.

15.7k views

retagged Jul 1, 2017

6 answers

29

CMI2010-B-04b
Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers. A DFA that has $n$ states and accepts an infinite language must accept at least one string $x$ such that $2n < |x| < 3n$, where $|x|$ denotes the length of $x$.

Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.A DFA that has $n$ states and accepts an infinite la...

4.1k views

retagged Jul 1, 2017

9 answers

30

GATE CSE 2017 Set 2 | Question: 25
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left | w_{1} \right | = 2, \left | w_{2} \right |\geq 3$} is ______________ .

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$ | $w_{1},w_{2}$ $\in$ $\left \{ a,b \righ...

16.6k views

retagged Jul 1, 2017

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