Dark Mode

Recent questions tagged tbb-toc-1

6 votes

2 answers

1

Test by Bikram | Theory of Computation | Test 1 | Question: 30
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is: Decidable Undecidable but semi-decidable Not even semi-decidable Indeterminable

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

601 views

0 votes

1 answer

2

Test by Bikram | Theory of Computation | Test 1 | Question: 29
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an: Decidable problem Undecidable problem Cannot ascertain None

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

168 views

0 votes

1 answer

3

Test by Bikram | Theory of Computation | Test 1 | Question: 28
Recursive Enumerable Languages are NOT closed under : Union Intersection Complement Homomorphism

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

79 views

0 votes

1 answer

4

Test by Bikram | Theory of Computation | Test 1 | Question: 27
If $S$ and $T$ are languages over $\Sigma =\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$ respectively, then which of the following options is CORRECT? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \emptyset$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

84 views

1 vote

1 answer

5

Test by Bikram | Theory of Computation | Test 1 | Question: 26
$L1$ and $L2$ are regular languages. $L3$ is CFL and $L4$ is a recursive enumerable language. $L5$ is the reversal of $L4$. If $L6= \{ (L3/y)$ intersection $L5 \}$ where $y$ is input alphabet, then $L6$ is a: Regular Language CFL Recursive Enumerable Language Non Recursive Enumerable Language

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

396 views

4 votes

1 answer

6

Test by Bikram | Theory of Computation | Test 1 | Question: 25
If all the strings of a language can be enumerated in $\text{lexicographic}$ order, then this is an example of a _______ language. Regular CFL but need not be regular CSL but need not be a CFL Recursive but need not be a CSL

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

387 views

0 votes

0 answers

7

Test by Bikram | Theory of Computation | Test 1 | Question: 24
By reading any string, which of the following is possible for a Turing Machine? TM halts in Final State TM halts in Non Final State TM enters into Infinite Loop All of these

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

75 views

1 vote

2 answers

8

Test by Bikram | Theory of Computation | Test 1 | Question: 23
PDA can be used for: infix to postfix conversion implementing recursive function calls evaluating arithmetic expressions all of the above

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

137 views

3 votes

2 answers

9

Test by Bikram | Theory of Computation | Test 1 | Question: 22
Total Recursive Functions are similar to: Recursive Languages Recursive Enumerable Languages Cannot relate the two None

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

355 views

4 votes

2 answers

10

Test by Bikram | Theory of Computation | Test 1 | Question: 21
Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$ The number of derivation trees for the string $\text{id} +\text{id} ^* \text{id} – \text{id}$ is: $5$ $6$ $7$ $8$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

344 views

2 votes

1 answer

11

Test by Bikram | Theory of Computation | Test 1 | Question: 20
Which of the following is not a Regular Expression? $[(a+b)^* – (aa+bb)]^*$ $[(0+1) – (0b + a1)^* (a+b)]^*$ $(01+11+10)^*$ $(1+2+0)^* (1+2)^*$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

350 views

3 votes

1 answer

12

Test by Bikram | Theory of Computation | Test 1 | Question: 19
Consider the following CFG : $S \rightarrow AB$ $A \rightarrow BC \mid a$ $B \rightarrow CC \mid b$ $C \rightarrow a \mid AB$ The Rank of Variable $A$ is: $2$ $3$ $4$ not possible to define

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

525 views

1 vote

1 answer

13

Test by Bikram | Theory of Computation | Test 1 | Question: 18
The regular set $A =(01+1)^*$ and the regular set $B =((01)^*1^*)^*$ Which of the following statements is TRUE? $A$ is a subset of $B$ $B$ is a subset of $A$ $A$ and $B$ are incomparable $A=B$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

113 views

2 votes

2 answers

14

Test by Bikram | Theory of Computation | Test 1 | Question: 17
The language $L =\{a^n \ b^n \mid n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is: DCFL CFL but not DCFL Non-CFL Regular Language

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

227 views

2 votes

1 answer

15

Test by Bikram | Theory of Computation | Test 1 | Question: 16
The Minimal Finite Automata accepting the set of all strings over $(0+1)^*$ that do NOT have the sub-string $0001$ has: $5$ states $6$ states $7$ states $9$ states

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

217 views

0 votes

3 answers

16

Test by Bikram | Theory of Computation | Test 1 | Question: 15
Which one is a correct statement in terms of accepting powers of DPDA and NPDA? DPDA and NPDA are equal DPDA and NPDA are not comparable DPDA < NPDA DPDA > NPDA

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

93 views

0 votes

2 answers

17

Test by Bikram | Theory of Computation | Test 1 | Question: 14
Consider the grammar given below : $S \rightarrow AB \mid DA$ $B \rightarrow BCD \mid ABD \mid CC \mid b$ $A \rightarrow a \mid BC$ $C \rightarrow aBD \mid a$ $C \rightarrow aBCAD \mid DaB$ $A \rightarrow aBCAD \mid Da$ ... following non terminal is useless in the grammar (as non terminal strings can be derived from it): $D$ $C$ $B$ $A$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

202 views

6 votes

1 answer

18

Test by Bikram | Theory of Computation | Test 1 | Question: 13
An NFA has $10$ states out of which $3$ are final states. The maximum number of final states in converted DFA is: $895$ $894$ $896$ $897$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

567 views

0 votes

1 answer

19

Test by Bikram | Theory of Computation | Test 1 | Question: 12
Let $N(f) =$ the class of languages accepted by Non- deterministic Finite Automata, $N(p) =$ the class of languages accepted by Non- deterministic Push down Automata, $D(f)=$ the class of languages accepted by Deterministic Finite Automata; and, $D(p)=$ the class of ... $D(p) = N(p)$ $D(f) = N(f)$ and $D(p)$ subset of $N(p)$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

97 views

2 votes

2 answers

20

Test by Bikram | Theory of Computation | Test 1 | Question: 11
Identify the Regular Expression among the following which denotes ALL strings of $a$'s and $b$'s, where each string contains at least $2$ $b$'s: $(a+b)^*ba^*b$ $(a+b)^*ba^*ba$ $(a+b)^*ba^*b(a+b)^*$ $(a+b)^*ab^*ab$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

186 views

1 vote

1 answer

21

Test by Bikram | Theory of Computation | Test 1 | Question: 10
Consider the language $L =\{ ab^2 wb^3 / w$ is an element of $(a+b)^* \}$. $L$, therefore, is: regular CFL but not regular CSL but not CFL none

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

152 views

1 vote

1 answer

22

Test by Bikram | Theory of Computation | Test 1 | Question: 9
Regular Languages are not closed under ______ operator. Union Concatenation Subset Division

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

198 views

2 votes

1 answer

23

Test by Bikram | Theory of Computation | Test 1 | Question: 8
Which of the following sets can be recognized by a Deterministic Finite State Automation? The numbers $2^0, \ 2^1$ to $2^n$ written in unary. The numbers $2^0, \ 2^1$ to $2^n$ written in binary. The set of binary strings where the number of zeros is the same as the number of ones. The set $\{1,101,11011,1110111, \dots \}$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

290 views

1 vote

1 answer

24

Test by Bikram | Theory of Computation | Test 1 | Question: 7
How many states are there in the minimal DFA that accept the following language? $L= \{x \mid x$ is a binary string with number of $0$'s divisible by $2$ and number of $1$'s divisible by $3 \}$ $6$ $5$ $3$ $2$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

160 views

4 votes

1 answer

25

Test by Bikram | Theory of Computation | Test 1 | Question: 6
If L is any regular language accepted by Minimal Finite Automaton with $n$ states, then the number of states in Minimal Finite Automaton to accept Prefix(L) is: $n$ $n+1$ $n+2$ $2n$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

491 views

3 votes

0 answers

26

Test by Bikram | Theory of Computation | Test 1 | Question: 5
If a language L1 is polynomially reduced to the language L2 and L2 is polynomially reduced to the language L1, then which of the following cannot be TRUE? L1 is decidable and L2 is undecidable. L1 is regular and L2 is CFL. L1 is recursive and L2 is recursively enumerable. L1 is decidable and L2 is decidable.

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

446 views

1 vote

1 answer

27

Test by Bikram | Theory of Computation | Test 1 | Question: 4
If $r1$ ,$r2$ and $r3$ are the accepting powers of DFA, NFA and NFA with Epsilon - moves, then ____________. $r1=r2=r3$ $r1 < r2 = r3$ $r1 = r2 < r3$ $r1$ not equal to $r2$ not equal to $r3$

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

103 views

3 votes

1 answer

28

Test by Bikram | Theory of Computation | Test 1 | Question: 3
Which of the following grammars violate the Chomsky Normal Form? $S \rightarrow AB$, $A \rightarrow a , B \rightarrow \epsilon \mid b$ $S \rightarrow AcB, A \rightarrow a, B \rightarrow b$ $S \rightarrow AB, \ A \rightarrow a, \ B \rightarrow b$ All of the above (i) only (i) and (ii) only (ii) and (iii) only

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

226 views

1 vote

1 answer

29

Test by Bikram | Theory of Computation | Test 1 | Question: 2
The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states.

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

235 views

1 vote

1 answer

30

Test by Bikram | Theory of Computation | Test 1 | Question: 1
Let $L$ denote the language generated by the grammar $S \rightarrow 00T$, $T \rightarrow 11S \mid 11$. If $S$ is the start symbol, then which among the following options is TRUE? $L = (0+1)^*$ $L$ is regular but not $(0+1)^*$ $L$ is context free but not regular $L$ is not context free

Bikram asked in Theory of Computation Nov 26, 2016

by Bikram

221 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged tbb-toc-1