Register

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
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:DecidableUndecidable but semi-decida...
User Avatar
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
$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 prob...
User Avatar
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
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
User Avatar
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
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 ...
User Avatar
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
By reading any string, which of the following is possible for a Turing Machine?TM halts in Final StateTM halts in Non Final StateTM enters into Infinite LoopAll of these
User Avatar
1 votes
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
PDA can be used for:infix to postfix conversionimplementing recursive function callsevaluating arithmetic expressionsall of the above
User Avatar
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
Total Recursive Functions are similar to:Recursive LanguagesRecursive Enumerable LanguagesCannot relate the twoNone
User Avatar
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$
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} ^* \t...
User Avatar
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)^*$
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)^*$
User Avatar
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
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...
User Avatar
1 votes
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$
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 ...
User Avatar
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
The language $L =\{a^n \ b^n \mid n \geq 1\} \cup \{a^m \ b^{2m} \mid m \geq 1\}$ is:DCFLCFL but not DCFLNon-CFLRegular Language
User Avatar
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
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
User Avatar
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
Which one is a correct statement in terms of accepting powers of DPDA and NPDA?DPDA and NPDA are equalDPDA and NPDA are not comparableDPDA < NPDADPDA NPDA
User Avatar
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$
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$
User Avatar
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$
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^*...
User Avatar
1 votes
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
Consider the language $L =\{ ab^2 wb^3 / w$ is an element of $(a+b)^* \}$.$L$, therefore, is:regularCFL but not regularCSL but not CFLnone
User Avatar
1 votes
1 answer
22
Test by Bikram | Theory of Computation | Test 1 | Question: 9
Regular Languages are not closed under ______ operator. Union Concatenation Subset Division
Regular Languages are not closed under ______ operator.UnionConcatenationSubsetDivision
User Avatar
1 votes
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$
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$...
User Avatar
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$
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...
User Avatar
1 votes
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$
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$ n...
User Avatar
1 votes
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.
The minimal DFA that accepts all strings of a's and b's, and ends with 'aa' has _____ number of states.
User Avatar
To see more, click for the full list of questions or popular tags.