The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent activity by Praveen Saini
User Praveen Saini
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Praveen Saini
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
8
answers
1
GATE2015235
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 nonterminals 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$ ... $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

4.8k
views
gate20152
theoryofcomputation
regulargrammar
normal
2
answers
2
GATE2016242
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

7.1k
views
gate20162
theoryofcomputation
finiteautomata
normal
5
answers
3
GATE20138
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

5k
views
gate2013
theoryofcomputation
normal
regularlanguages
2
answers
4
Minimum NAND/NOR Gates  Realization for ExOR,ExNor,Adder,Subtractor
Minimum No of Gates NAND/NOR ExOR ExNor Half Adder Half Subtractor Full Adder Full Subtractor NAND ? ? ? ? ? ? NOR ? ? ? ? ? ?
commented
Aug 10, 2019
in
Digital Logic

59.5k
views
3
answers
5
Why L = { w x w ∣ w , x ∈ ( a + b ) + } is not regular?
We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a Please expleain where I am wrong
commented
Jul 26, 2019
in
Theory of Computation

983
views
theoryofcomputation
regularlanguages
decidability
5
answers
6
GATE20162GA10
$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

1.7k
views
gate20162
numericalability
datainterpretation
normal
4
answers
7
GATE200553
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

2.7k
views
gate2005
theoryofcomputation
finiteautomata
normal
1
answer
8
GATE200111b
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, ... be used to design the circuit. Give the minimized sumofproduct expression for J and K inputs of one of its state flipflops
commented
Jul 8, 2019
in
Digital Logic

683
views
gate2001
digitallogic
normal
descriptive
flipflop
8
answers
9
GATE199117,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a nondeterministic 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

2.7k
views
gate1991
theoryofcomputation
finiteautomata
normal
1
answer
10
What is the minimum pumping length of the following languages
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

3.4k
views
theoryofcomputation
pumpinglemma
3
answers
11
The boolean expression f(x,y,z) in its canonical form for the decoder circuit shown below is
commented
Mar 10, 2019
in
Digital Logic

854
views
digitallogic
2
answers
12
GATE2019GA10
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 ... Z: I believe in Vaastu and so I want to stay in SouthWest wing. The shaded rooms are already occupied. WR is washroom
answer selected
Feb 7, 2019
in
Numerical Ability

2.1k
views
gate2019
generalaptitude
numericalability
directionsense
1
answer
13
what is the regular expression equivalent to the DFA ?
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

414
views
1
answer
14
dfa min states
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.1k
views
theoryofcomputation
minimalstateautomata
3
answers
15
GATE20012.12
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

3k
views
gate2001
digitallogic
normal
synchronousasynchronouscircuits
7
answers
16
GATE200941
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

3k
views
gate2009
theoryofcomputation
finiteautomata
easy
1
answer
17
Is this language regular? L1:{wxwR∣w,x∈{a,b}∗ and w,x>0},wR is the reverse of string w
commented
Dec 29, 2018

479
views
theoryofcomputation
3
answers
18
GATE2016216
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.
commented
Dec 29, 2018
in
Theory of Computation

2.8k
views
gate20162
theoryofcomputation
finiteautomata
normal
numericalanswers
minimalstateautomata
3
answers
19
GATE19952.23
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

2.6k
views
gate1995
theoryofcomputation
finiteautomata
normal
4
answers
20
GATE2014315
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

3.2k
views
gate20143
theoryofcomputation
regularexpressions
numericalanswers
easy
2
answers
21
GATE200635
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

2.9k
views
gate2006
digitallogic
circuitoutput
normal
2
answers
22
GATE19981.10
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

3.7k
views
gate1998
theoryofcomputation
finiteautomata
normal
1
answer
23
GATE199813
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.2k
views
gate1998
theoryofcomputation
pushdownautomata
descriptive
3
answers
24
GATE20001.5
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

2.6k
views
gate2000
theoryofcomputation
easy
identifyclasslanguage
3
answers
25
GATE2014116
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

1.9k
views
gate20141
theoryofcomputation
finiteautomata
easy
3
answers
26
GATE19982.5
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

4.2k
views
gate1998
theoryofcomputation
finiteautomata
normal
minimalstateautomata
3
answers
27
How is the complement of Language L is Context free ??
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

2.3k
views
theoryofcomputation
contextfreelanguages
contextsensitive
3
answers
28
TIFR2014B12
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 ... 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.4k
views
tifr2014
theoryofcomputation
regularlanguages
5
answers
29
GATE200927
Given the following state table of an FSM with two states $A$ and $B$ ... 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

3.4k
views
gate2009
theoryofcomputation
finiteautomata
normal
1
answer
30
GATE199319
A control algorithm is implemented by the NAND – gate circuitry given in figure below, where $A$ and $B$ are state variable implemented by $D$ flipflops, and $P$ is control input. Develop the state transition table for this controller.
commented
Aug 7, 2018
in
Digital Logic

1.2k
views
gate1993
digitallogic
circuitoutput
normal
descriptive
5
answers
31
GATE200685
The grammar $S\rightarrow AC\mid CB$ $C\rightarrow aCb\mid \epsilon$ $A\rightarrow aA\mid a$ $B\rightarrow Bb\mid b$ generates the language $ L=\left \{ a^{i}b^{j}\mid i\neq j \right \}$. In this grammar what is the length of the derivation (number of steps starting from $S$) to generate the string $a^{l}b^{m}$ with $l\neq m$ $\max (l,m) + 2$ $l + m + 2$ $l + m + 3$ $\max (l,m) + 3$
answered
Jun 24, 2018
in
Compiler Design

1.3k
views
gate2006
compilerdesign
grammar
normal
5
answers
32
GATE2007IT50
Consider the following finite automata $P$ and $Q$ over the alphabet $\{a, b, c\}$. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by $L(P)$ and $L(Q)$ respectively. The automation which recognizes the language $L(P) \cap L(Q)$ is :
commented
May 31, 2018
in
Theory of Computation

3.7k
views
gate2007it
theoryofcomputation
finiteautomata
normal
6
answers
33
GATE2007IT47
Consider the following DFA in which $S_0$ is the start state and $S_1$, $S_3$ are the final states. What language does this DFA recognize? All strings of $x$ and $y$ All strings of $x$ and $y$ which have either even number of $x$ and even number of $y$ or odd number of ... of $x$ and $y$ with either even number of $x$ and odd number of $y$ or odd number of $x$ and even number of $y$
commented
May 8, 2018
in
Theory of Computation

1.3k
views
gate2007it
theoryofcomputation
finiteautomata
normal
2
answers
34
GATE2006IT3
In the automaton below, $s$ is the start state and $t$ is the only final state. Consider the strings $u = abbaba, v = bab, \text{and} w = aabb$. Which of the following statements is true? The automaton accepts $u$ and $v$ but not $w$ The automaton accepts each of $u, v,$ and $w$ The automaton rejects each of $u, v,$ and $w$ The automaton accepts $u$ but rejects $v$ and $w$
commented
May 8, 2018
in
Theory of Computation

1k
views
gate2006it
theoryofcomputation
finiteautomata
normal
2
answers
35
ISRO201330
In a three stage counter, using RS flip flops what will be the value of the counter after giving $9$ pulses to its input? Assume that the value of counter before giving any pulses is 1. 1 2 9 10
commented
May 3, 2018
in
Digital Logic

2.8k
views
isro2013
digitallogic
flipflop
1
answer
36
can we find out minimum numbers of states in DFA if NFA has n states
commented
Mar 3, 2018
in
Theory of Computation

3.7k
views
2
answers
37
GATE19997
Show that the language $L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$ is not context free. $c$ is not $0$ or $1$.
commented
Feb 21, 2018
in
Theory of Computation

1.2k
views
gate1999
theoryofcomputation
contextfreelanguages
normal
5
answers
38
GATE201852
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i1} \bullet L \text{ for all } I >0$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____
answered
Feb 14, 2018
in
Theory of Computation

6.4k
views
gate2018
theoryofcomputation
numericalanswers
regularlanguages
2
answers
39
GATE2012 AR: GA6
A value of $x$ that satisfies the equation $\log x + \log (x – 7) = \log (x + 11) + \log 2$ is $1$ $2$ $7$ $11$
commented
Jan 29, 2018
in
Numerical Ability

332
views
gate2012ar
numericalability
numericalcomputation
logarithms
8
answers
40
GATE201041
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in nondeterministic finite automation that accepts $L$? $n1$ $n$ $n+1$ $2^{n1}$
commented
Jan 29, 2018
in
Theory of Computation

5k
views
gate2010
theoryofcomputation
finiteautomata
normal
minimalstateautomata
50,737
questions
57,275
answers
198,154
comments
104,817
users