Questions by Bikram / GATE Overflow for GATE CSE

0 votes

1 answer

31

Test by Bikram | Theory of Computation | Test 2 | Question: 30
The language generated by the following grammar is: $S \rightarrow aAb$ $A \rightarrow aAb / B$ $B \rightarrow CC$ $C \rightarrow bDa$ $D \rightarrow bDa / \epsilon$ $\{ {a^m \;b^n \;a^n\; b^p \;a^p\; b^m } \mid m,n,p > 0\;\}$ ... $\{ { a^m\; b^m \;a^n\; b^n \;a^p\; b^p } \mid m,n,p > 0\; \}$

The language generated by the following grammar is:$S \rightarrow aAb$$A \rightarrow aAb / B$$B \rightarrow CC$$C \rightarrow bDa$$D \rightarrow bDa / \epsilon$$\{ {a...

302 views

asked Aug 12, 2017

4 votes

0 answers

32

Test by Bikram | Theory of Computation | Test 2 | Question: 29
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is _______ .

The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...

630 views

asked Aug 12, 2017

0 votes

1 answer

33

Test by Bikram | Theory of Computation | Test 2 | Question: 28
What is the regular expression corresponding to the above DFA? $(01 + (00)^*1)^*$ $0^*10^*$ $(10 + 0(00)^* (1 + 01) )^*$ $0(00)^*10^*$

What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$

285 views

asked Aug 12, 2017

1 votes

0 answers

34

Test by Bikram | Theory of Computation | Test 2 | Question: 27
Which of the following regular expressions does not generate the following language? $\{w \mid \text{ the length of }w \text{ is at most }4\} \text{ where } \Sigma = \{a,b\}$ ... $( \epsilon + \Sigma) ( \epsilon + \Sigma) ( \epsilon + \Sigma) ( \epsilon + \Sigma)$

Which of the following regular expressions does not generate the following language?$\{w \mid \text{ the length of }w \text{ is at most }4\} \text{ where } \Sigma = \{a,b...

449 views

asked Aug 12, 2017

1 votes

1 answer

35

Test by Bikram | Theory of Computation | Test 2 | Question: 26
Given below are two regular languages : $L1 = \{ W / W \text{ in } \{0,1\}^* \text{and each string starts with } 0'.\}$ $L2 = \{ W / W \text{ in } \{0,1\}^* \text{ and each string ends with } 1' \}$ Which one of the following ... $\{W / W \in \{0,1\}^* \text{ and each string starts with 0' and ends with 1' } \}$

Given below are two regular languages :$L1 = \{ W / W \text{ in } \{0,1\}^* \text{and each string starts with }‘0’.\}$$L2 = \{ W / W \text{ in } \{0,1\}^* \text{ ...

203 views

asked Aug 12, 2017

2 votes

1 answer

36

Test by Bikram | Theory of Computation | Test 2 | Question: 25
Which of the following are regular? $\{aba^R \mid a,b \in \{0,1\}^+ \}$ $\{aba \mid a,b \in \{0,1\}^* \}$ $\{aba^R \mid b,a \in \{0,1\}^* \text{ and } \mid b \mid = 10 \}$ (i) and (iii) only (i) and (ii) only (i) only (ii) and (iii) only

Which of the following are regular?$\{aba^R \mid a,b \in \{0,1\}^+ \}$ $\{aba \mid a,b \in \{0,1\}^* \}$$\{aba^R \mid b,a \in \{0,1\}^* \text{ and } \mid b \mid = 10 \...

446 views

asked Aug 12, 2017

2 votes

2 answers

37

Test by Bikram | Theory of Computation | Test 2 | Question: 24
Consider the following Pushdown Automata Transition Function $\delta$ : 1. $\delta ( q_0 , \epsilon, z_0 ) = ( q_0 , \epsilon)$ 2. $\delta ( q_0 , 0, z_0 ) = ( q_0 , xz_0 )$ 3. $\delta ( q_0 , 0, x ) = ( q_1 , x)$ ... $\{0^{2n} 1^n \mid n \geq 0\}$ $\{0^{2n} 1^{2n} \mid n \geq 0\}$

Consider the following Pushdown Automata Transition Function $\delta$ :1. $\delta ( q_0 , \epsilon, z_0 ) = ( q_0 , \epsilon)$2. $\delta ( q_0 , 0, z_0 ) = (...

537 views

asked Aug 12, 2017

2 votes

1 answer

38

Test by Bikram | Theory of Computation | Test 2 | Question: 23
Match the following lists. The conditions on the language description $L = \{a^i \ b^j \ c^k\}$ ... $A:G_3, B:G_2, C:G_1$ $A:G_1, B:G_3, C:G_2$ $A:G_3, B:G_1, C:G_2$

Match the following lists.The conditions on the language description $L = \{a^i \ b^j \ c^k\}$ are given in List I and respective grammars are given in List II.$\begin{ar...

208 views

asked Aug 12, 2017

3 votes

1 answer

39

Test by Bikram | Theory of Computation | Test 2 | Question: 22
Let L be the set of strings on $\Sigma = (0,1)$ such that $z$ belongs to $L$ if number of $0$' s in $z$ is divisible by $k. \ k \geq 2$ and number of $1$' s in $z$ is odd. The number of states in the minimal DFA which accept the language $L$ is ______.

Let L be the set of strings on $\Sigma = (0,1)$ such that $z$ belongs to $L$ if number of $0$' s in $z$ is divisible by $k. \ k \geq 2$ and number of $1$' s in $z$ is odd...

503 views

asked Aug 12, 2017

0 votes

1 answer

40

Test by Bikram | Theory of Computation | Test 2 | Question: 21
A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. Then, which of the following statements are true? S1 : $X$ is NP complete and $Y$ is in NP. S2 : $X$ is NP complete and ... hard. S4 : $X$ and $Y$ are NP hard. S4 only S1, S2 & S3 S3 & S4 S1, S2, S3 & S4

A problem $X$ is reducible to problem $Y$ in polynomial time. All the problems in NP can also be reduced to problem $X$. Then, which of the following statements are true?...

672 views

asked Aug 12, 2017

0 votes

1 answer

41

Test by Bikram | Theory of Computation | Test 2 | Question: 20
Which of the following pairs of regular expressions define the same language $\{a, b\}$? $(a^*+ b^*) ^*$ and $(a+ b)^*$ $(a^* b )^* a^*$ and $a(ba^* )^*$ $(a^*+ b)^*$ and $(a+ b)^*$ $(a b)^* a$ and $a (ba)^*$ $a, b$, and $d$ $a, c$, and $d$ $b,c,d$ $a,b,c$ and $d$

Which of the following pairs of regular expressions define the same language $\{a, b\}$?$(a^*+ b^*) ^*$ and $(a+ b)^*$$(a^* b )^* a^*$ and $a(ba^* )^*$$(a^*+ b)^*$ and...

252 views

asked Aug 12, 2017

0 votes

1 answer

42

Test by Bikram | Theory of Computation | Test 2 | Question: 19
Which of the following statements is correct about the given Turing Machine transitions below? ... in $\Sigma ^*$. TM halts on all strings of even length. I and II II and IV II and III I , II and III

Which of the following statements is correct about the given Turing Machine transitions below?$\begin{array}{|c|c|c|c|} \hline \delta & 0 & 1 & B \\ \hline q0 & (q1,1,R) ...

453 views

asked Aug 12, 2017

1 votes

1 answer

43

Test by Bikram | Theory of Computation | Test 2 | Question: 18
Which of the following languages is/are deterministic context-free? $L_1 = \{ ww^R \mid w \in \{a,b\}^* \text{ and } w^R \text{ is reverse of } w \}$ $L_2 = \{ ww^R x \mid w, x \in \{0,1\}^* \}$ $L1$ only $L2$ only Both $L1$ and $L2$ Neither $L1$ nor $L2$

Which of the following languages is/are deterministic context-free?$L_1 = \{ ww^R \mid w \in \{a,b\}^* \text{ and } w^R \text{ is reverse of } w \}$$L_2 = \{ ww^R x \mi...

492 views

asked Aug 12, 2017

1 votes

0 answers

44

Test by Bikram | Theory of Computation | Test 2 | Question: 17
Match the following statements with True (T) / False (F) : $S1: \ CFG = \{ <G> \mid \text{ G is a CFG and } L (G) = \Sigma ^* \} \text{ is undecidable}$ ... , S2 - F, S3 - T , S4 - T S2 - T, S3 - F, S1 - T , S4 - T S1 - T, S2 - F, S3 - T , S4 - F

Match the following statements with True (T) / False (F) :$S1: \ CFG = \{ <G \mid \text{ G is a CFG and } L (G) = \Sigma ^* \} \text{ is undecidable}$$S2: \ A = \{ <G \mi...

434 views

asked Aug 12, 2017

0 votes

0 answers

45

Test by Bikram | Theory of Computation | Test 2 | Question: 16
Consider the following incomplete DFA. What will be the transitions of state D such that automata will accept the set of all binary strings containing $010$ as sub-string ? $d (D,0)=A$ $d (D,1)=D$ $d (D,0)=C$ $d (D,1)=B$ $d (D,0)=D$ $d (D,1)=B$ $d (D,0)=D$ $d (D,1)=D$

Consider the following incomplete DFA.What will be the transitions of state D such that automata will accept the set of all binary strings containing $010$ as sub-string ...

236 views

asked Aug 12, 2017

0 votes

1 answer

46

Test by Bikram | Theory of Computation | Test 2 | Question: 15
Which of the following languages is regular? $L = \{ bba (ba)^* a^{n-1} \mid n> 0 \}$ $L = \{a^nb^n \mid n < 1000 \}$ $L = \{a^nb^k \mid \text{ n is odd or k is even} \}$ $L = \{ wxw^R \mid w,x \in (0+1)^* \}$ $1$, $3$ and $4$ $2, 3, 4$ $2, 3$ $1, 2, 3, 4$

Which of the following languages is regular?$L = \{ bba (ba)^* a^{n-1} \mid n 0 \}$$L = \{a^nb^n \mid n < 1000 \}$$L = \{a^nb^k \mid \text{ n is odd or k is even} \}$$L ...

446 views

asked Aug 12, 2017

1 votes

1 answer

47

Test by Bikram | Theory of Computation | Test 2 | Question: 14
Which of the following is correct? $(01 )^* \cap (10)^* = \not{0}$ $(x + y + z)^* = x^*y^*z^* + x^*y^* + z^* + z^*x^*y^*$ $(p + q )^* p + ( p+q)^* q + \epsilon = (p^* q^*)^*$ $(m + n)^* \cap (m + n)^* mn \neq (m + n)^* mn$

Which of the following is correct?$(01 )^* \cap (10)^* = \not{0}$$(x + y + z)^* = x^*y^*z^* + x^*y^* + z^* + z^*x^*y^*$$(p + q )^* p + ( p+q)^* q + \epsilon = (p^* q^...

362 views

asked Aug 12, 2017

0 votes

1 answer

48

Test by Bikram | Theory of Computation | Test 2 | Question: 13
Which of the following statements are NOT true? Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$. Given two arbitrary context-free grammars $G1$ and $G2$ ... a particular non-terminal "X" in G is reachable. I,IV and II II and IV I and IV I,II and III

Which of the following statements are NOT true?Given two regular grammars $G1$ and $G2$, it is undecidable whether $L (G1) = L (G2)$.Given two arbitrary context-free gram...

428 views

asked Aug 12, 2017

1 votes

1 answer

49

Test by Bikram | Theory of Computation | Test 2 | Question: 12
Choose the regular expression corresponding to the given DFA : $(00 ^*1 + 11^* 0) (0 + 1) ^*$ $((11) ^* 0 + 00 ^* 1)(0 + 1) ^*$ $(11) ^* (0 ^* 1 + 1^* 0) (0 + 1) ^*$ $(11) ^* (00 ^* 1 + 10) (0 + 1) ^*$

Choose the regular expression corresponding to the given DFA :$(00 ^*1 + 11^* 0) (0 + 1) ^*$$((11) ^* 0 + 00 ^* 1)(0 + 1) ^*$$(11) ^* (0 ^* 1 + 1^* 0) (0 + 1) ^*$$(11) ^*...

302 views

asked Aug 12, 2017

0 votes

2 answers

50

Test by Bikram | Theory of Computation | Test 2 | Question: 11
Consider the grammar given below: $S \rightarrow x \ T \mid y \ Z$ $Z \rightarrow x \mid x \ S \mid y \ Z \ Z$ $T \rightarrow y \mid y \ S \mid y \ T \ T$ Consider the following strings: $xxyyx$ $xxyyxy$ $xyxy$ ... Which of the above strings are generated by the given grammar? i, iv and iii ii, iii and iv ii, v and iv iii, iv and v

Consider the grammar given below:$S \rightarrow x \ T \mid y \ Z$$Z \rightarrow x \mid x \ S \mid y \ Z \ Z$$T \rightarrow y \mid y \ S \mid y \ T \ T$Consider the foll...

361 views

asked Aug 12, 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