Register

Recent questions tagged tbb-toc-2

0 0 votes
1 1 answer
669
669 views
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...
User Avatar
5 5 votes
0 0 answers
1.2k
1.2k views
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...
User Avatar
0 0 votes
1 answers 1 answer
667
667 views
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^*$
User Avatar
1 1 vote
0 0 answers
1.0k
1.0k views
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...
User Avatar
1 1 vote
1 answers 1 answer
441
441 views
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 ...
User Avatar
2 2 votes
1 answers 1 answer
1.1k
1.1k views
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 \...
User Avatar
2 2 votes
2 2 answers
1.3k
1.3k views
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 ) = (...
User Avatar
2 2 votes
1 1 answer
493
493 views
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\}$ are given in List I and respective grammars are given in List II.$\begin{ar...
User Avatar
3 3 votes
1 answers 1 answer
1.1k
1.1k views
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...
User Avatar
0 0 votes
1 answers 1 answer
1.6k
1.6k views
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?...
User Avatar
0 0 votes
1 answers 1 answer
640
640 views
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...
User Avatar
0 0 votes
1 answers 1 answer
1.3k
1.3k views
Test by Bikram | Theory of Computation | Test 2 | Question: 19
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) ...
User Avatar
1 1 vote
1 answers 1 answer
865
865 views
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 \mi...
User Avatar
1 1 vote
0 0 answers
1.0k
1.0k views
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: \ A = \{ <G \mi...
User Avatar
0 0 votes
1 1 answer
665
665 views
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 ...
User Avatar
0 0 votes
1 answers 1 answer
1.1k
1.1k views
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 ...
User Avatar
1 1 vote
1 answers 1 answer
821
821 views
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^...
User Avatar
0 0 votes
1 answers 1 answer
960
960 views
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 gram...
User Avatar
1 1 vote
1 answers 1 answer
639
639 views
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) ^*...
User Avatar
0 0 votes
2 answers 2 answers
743
743 views
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 foll...
User Avatar
0 0 votes
0 0 answers
607
607 views
Test by Bikram | Theory of Computation | Test 2 | Question: 10
Match the correct automation given in Y to its transition function in $X$:$\begin{array}{|l|l|} \hline {} & X & {} & Y \\ \hline I. & Q^* \Sigma \rightarrow Q & A. & \tex...
User Avatar
1 1 vote
1 answers 1 answer
959
959 views
Test by Bikram | Theory of Computation | Test 2 | Question: 9
Consider the following transition table of DFA where $q3$ is the final state:$\begin{array}{|c|c|c|} \hline {} & x & y \\ \hline \rightarrow q0 & q1 & q0 \\ \hline q1 & q...
User Avatar
0 0 votes
1 answers 1 answer
548
548 views
Test by Bikram | Theory of Computation | Test 2 | Question: 8
Which of the following Regular Expression is NOT the same as the other three?$100 ( ( (00)^* (10)^* )^* 100)^*$$100 ( ( ( 0+1) 0)^* 100 )^*$$100 ( (00 + 10)^* 100)^*$$10...
User Avatar
2 2 votes
3 answers 3 answers
1.3k
1.3k views
Test by Bikram | Theory of Computation | Test 2 | Question: 7
Consider the following regular languages:$L_1$: Languages that accept strings over $\Sigma = \{a, b\}$, such that length of string is greater than $1$, but multiple of $3...
User Avatar
1 1 vote
1 answers 1 answer
619
619 views
Test by Bikram | Theory of Computation | Test 2 | Question: 6
How many states does the Minimal Finite Automata that accepts all strings of $x$'s and $z$'s (where the number of $x$'s is at least $L$) contain?$L$ states$(L+1)$ states$...
User Avatar
3 3 votes
2 answers 2 answers
1.6k
1.6k views
Test by Bikram | Theory of Computation | Test 2 | Question: 5
Given two regular expressions:$p = (0^* 1^* )^*$ and $q = 0^* + 1^* + 0^*1 + 10^*$The length of the smallest string that is present in the language corresponding to reg...
User Avatar
0 0 votes
1 answers 1 answer
1.1k
1.1k views
Test by Bikram | Theory of Computation | Test 2 | Question: 4
Which of the following statements is FALSE?Recursive Enumerable Languages are not closed under set difference and complementation.Complement of context-free language must...
User Avatar
1 1 vote
1 answers 1 answer
1.7k
1.7k views
Test by Bikram | Theory of Computation | Test 2 | Question: 3
Consider the following input sequence $010101\dots$ ($01$ repeated one or more times).The minimum number of states required in a DFA to accept the strings following the a...
User Avatar
1 1 vote
1 answers 1 answer
1.9k
1.9k views
Test by Bikram | Theory of Computation | Test 2 | Question: 2
Which of the following is correct?$(01)^* \cap (10)^* = \phi$$(a + b + c)^* = a^*b^*c^* + a^*b^* + c^* + c^*a^*b^*$$(p + q)^* p + (p + q)^* q + \epsilon = (p^* q^*)^*$$( ...
User Avatar
7 7 votes
1 answers 1 answer
2.0k
2.0k views
Test by Bikram | Theory of Computation | Test 2 | Question: 1
Choose the appropriate context-free language $L_2$ that ensure that $L_1 \cap L_2$ is NOT context-free, where $L_1 = \{x^ny^m z^m \mid m 0, n 0 \}$:$L_2 = \{x^n y^n z...
User Avatar
To see more, click for the full list of questions or popular tags.