search
Log In

Recent activity by Praveen Saini

10 answers
1
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
commented Aug 10, 2019 in Theory of Computation 6.4k views
2 answers
2
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false
commented Aug 10, 2019 in Theory of Computation 9.8k views
5 answers
3
Consider the languages $L_1 = \phi$ and $L_2 = \{a\}$. Which one of the following represents $L_1 {L_2}^* \cup {L_1}^*$ ? $\{\epsilon\}$ $\phi$ $a^*$ $\{\epsilon, a\}$
commented Aug 10, 2019 in Theory of Computation 7k views
3 answers
4
Minimum No of Gates NAND/NOR Ex-OR Ex-Nor Half Adder Half Subtractor Full Adder Full Subtractor NAND ? ? ? ? ? ? NOR ? ? ? ? ? ?
commented Aug 10, 2019 in Digital Logic 62.8k views
3 answers
5
5 answers
6
$f(x) = 1 - |x - 1|$ $f(x) =1 + |x - 1|$ $f(x) = 2 - |x - 1|$ $f(x) = 2 + |x - 1|$
commented Jul 25, 2019 in Numerical Ability 2.1k views
4 answers
7
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in $w$ is followed by exactly two $b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in $w$ is followed by at least two $b$'s} \right\}$ ... $ contains the substring $abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ | $w$ does not contain $aa$' as a substring} \right\}$
commented Jul 25, 2019 in Theory of Computation 3.9k views
1 answer
8
A sequential circuit takes an input stream of 0's and 1's and produces an output stream of 0's and 1's. Initially it replicates the input on its output until two consecutive 0's are encountered on the input. From then onward, it produces an output stream, which is ... to be used to design the circuit. Give the minimized sum-of-product expression for J and K inputs of one of its state flip-flops
commented Jul 8, 2019 in Digital Logic 1k views
8 answers
9
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
commented Jun 28, 2019 in Theory of Computation 3.9k views
1 answer
10
This is from the first chapter questions of Sipser's book on TOC. I am stuck in some of the questions where we are asked to find the pumping length of the following languages. Find the minimum pumping length of the following regular languages:- L=$0^*1^+0^+1^* \cup \ 10^*1$ L=001 U 0*1* L=0*1* L=10 (11* 0)* 0 L= ∊
comment edited Mar 19, 2019 in Theory of Computation 5.4k views
2 answers
12
Three of the five students are allocated to a hostel put in special requests to the warden, Given the floor plan of the vacant rooms, select the allocation plan that will accommodate all their requests. Request by X: Due to pollen allergy, I want to avoid a wing next to ... by Z: I believe in Vaastu and so I want to stay in South-West wing. The shaded rooms are already occupied. WR is washroom
answer selected Feb 7, 2019 in Numerical Ability 2.5k views
1 answer
13
I tried it through state elimination method but I am getting stucked at the outgoing edge from D to A .
commented Jan 10, 2019 in Theory of Computation 519 views
2 answers
14
find min no of states in dfa that accepts string begining or ending with 00 or 11
commented Jan 3, 2019 in Theory of Computation 1.3k views
4 answers
15
Consider the circuit given below with initial state $Q_0=1, Q_1=Q_2=0$. The state of the circuit is given by the value $4Q_2+2Q_1+Q_0$ Which one of the following is correct state sequence of the circuit? $1, 3, 4, 6, 7, 5, 2$ $1, 2, 5, 3, 7, 6, 4$ $1, 2, 7, 3, 5, 6, 4$ $1, 6, 5, 7, 2, 3, 4$
commented Dec 29, 2018 in Digital Logic 4.1k views
8 answers
16
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
commented Dec 29, 2018 in Theory of Computation 4.6k views
1 answer
17
Is this language regular? L1:{wxwR∣w,x∈{a,b}∗ and |w|,|x|>0}, wR is the reverse of string w Please explain..
commented Dec 29, 2018 in Unknown Category 646 views
4 answers
18
3 answers
19
A finite state machine with the following state table has a single input $x$ and a single out $z$ ... $01$ $10$ $101$ $110$
commented Oct 18, 2018 in Theory of Computation 3.7k views
5 answers
20
The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $a^*b^*(ba)^*a^*$
commented Oct 18, 2018 in Theory of Computation 4.4k views
2 answers
21
Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$ $x\bar{z}+xy+\bar{y}z$ $x\bar{z}+xy+\overline{yz}$ $xz+xy+\overline{yz}$ $xz+x\bar{y}+\bar{y}z$
commented Oct 17, 2018 in Digital Logic 4k views
2 answers
22
Which of the following set can be recognized by a Deterministic Finite state Automaton? The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary The numbers $1, 2, 4, 8,\dots 2^n, \dots$ written in unary The set of binary string in which the number of zeros is the same as the number of ones. The set $\{1, 101, 11011, 1110111, \dots\}$
commented Oct 17, 2018 in Theory of Computation 5.3k views
1 answer
23
Let $M=(\{q_0, q_1\}, \{0, 1\}, \{z_0, X\}, \delta, q_0, z_0, \phi)$ be a Pushdown automation where $\delta$ is given by $\delta(q_0, 1, z_0) = \{(q_0, Xz_0)\}$ $\delta(q_0, \epsilon, z_0) = \{(q_0, \epsilon)\}$ ... $\delta(q_0, 0, z_0) = \{(q_0, z_0)\}$ What is the language accepted by this PDA by empty stack? Describe informally the working of the PDA
commented Oct 17, 2018 in Theory of Computation 1.7k views
3 answers
24
Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$. Which of the following is TRUE? $L = 0^+$ $L$ is regular but not $0^+$ $L$ is context free but not regular $L$ is not context free
commented Oct 17, 2018 in Theory of Computation 3.7k views
5 answers
25
Consider the finite automaton in the following figure: What is the set of reachable states for the input string $0011$? $\{q_0,q_1,q_2\}$ $\{q_0,q_1\}$ $\{q_0,q_1,q_2,q_3\}$ $\{q_3\}$
commented Aug 7, 2018 in Theory of Computation 3.4k views
3 answers
26
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$ is $2$ $5$ $8$ $3$
commented Aug 7, 2018 in Theory of Computation 6.1k views
3 answers
27
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular (b) context free (c) context sensitive but not context free (d) recursive and not a cfl.
commented Aug 7, 2018 in Theory of Computation 3.1k views
3 answers
28
Consider the following three statements: Intersection of infinitely many regular languages must be regular. Every subset of a regular language is regular. If $L$ is regular and $M$ is not regular then $L ∙ M$ is necessarily not regular. Which of the following gives the correct true/ ... of the above? true, false, true. false, false, true. true, false, true. false, false, false. true, true, true.
commented Aug 7, 2018 in Theory of Computation 1.9k views
5 answers
29
Given the following state table of an FSM with two states $A$ and $B$ ... is the minimum length of an input string which will take the machine to the state $A=0,B=1$ with $output=1$. $3$ $4$ $5$ $6$
commented Aug 7, 2018 in Theory of Computation 4.5k views
1 answer
30
A control algorithm is implemented by the NAND – gate circuitry given in figure below, where $A$ and $B$ are state variable implemented by $D$ flip-flops, and $P$ is control input. Develop the state transition table for this controller.
commented Aug 7, 2018 in Digital Logic 1.5k views
...