Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions tagged finiteautomata
0
votes
2
answers
theory of computation
hi guys, I have a doubt if two DFA accept the same set of language then are they equal? why or why not? answer really appreciated
asked
Oct 24
in
Theory of Computation
by
rish1602
(
9
points)

46
views
toclanguages
finiteautomata
0
votes
0
answers
Self Doubt Theory of ComputationHow to distinguish when to use cross product, concatenation or Union in DFA?
asked
Oct 2
in
Theory of Computation
by
the_dalela
(
5
points)

9
views
finiteautomata
0
votes
1
answer
GradeUP Test Series
A traffic signal cycles from RED to YELLOW, YELLOW to GREEN, GREEN to RED. In each cycle RED is turned on for 50 seconds, YELLOW is turned on for 40 seconds and GREEN is turned on for 80 seconds. The traffic signal has to be implemented using a ... only input to this FSM is a clock of 10 second period. The minimum number of flip flops required to implement this FSM is _____.
asked
Aug 29
in
Digital Logic
by
Animesh Sinha
(
21
points)

54
views
gradeup
finiteautomata
digitallogic
0
votes
2
answers
Finite Automata
How to design a DFA for Σ = {0,1} that accepts the set of strings that contains at least two 0's and at most two 1's.
asked
Aug 25
in
Compiler Design
by
abhish1mishra
(
5
points)

35
views
theoryofcomputation
finiteautomata
theoryofcomputation
0
votes
1
answer
self doubt on regular languages
L = { w x (w^r)* ∣ w , x ∈ ( a + b ) * } is it regular language? If so, why? The notation W^r means the reverse string of W.
asked
Aug 18
in
Theory of Computation
by
abhijeet at
(
9
points)

34
views
regularlanguage
theoryofcomputation
finiteautomata
0
votes
0
answers
Deterministic Finite Automata
I need help in understanding the reasoning behind finding total number of states when positions of particular input is fixed from left hand side or right hand side. The Gate Overflow website shows the formula that for: nth position from the left side ... of states is 2n I want to understand the logic behind this generalized formula. How did we come to this conclusion?
asked
Aug 1
in
Theory of Computation
by
aryashah2k
(
2
points)

31
views
finiteautomata
theoryofcomputation
automata
dfadesign
0
votes
0
answers
Finite Languages and Automata Theory
Design a DFA (Deterministic Finite Automata) over the inputs {a,b} for Even number of a's and w mod 3 = 2. Basically it means we need ot create dfa such that the strings have even number of a's and at the same time, length of the string divide ... of 2. I know how to do for even number of a's but how to implement the condition of w mod 3 =2? Help needed
asked
Jul 24
in
Theory of Computation
by
aryashah2k
(
2
points)

34
views
theoryofcomputation
finiteautomata
dfadesign
automata
0
votes
0
answers
Gate2008IT200832
Why is it so that solving by converting from FA (state diagram given) to RE gives different solution as compared to ARDENS theorem. What is the RE of the state diagram , given in the question by using ARDENS theorem
asked
Jul 18
in
Theory of Computation
by
prajjwalsingh_11
(
15
points)

23
views
theoryofcomputation
finiteautomata
regularexpressions
ardenstheorem
+1
vote
0
answers
Theory of computation No of state in dfa
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?
asked
May 16
in
Theory of Computation
by
Shreya2002
(
9
points)

80
views
theoryofcomputation
finiteautomata
0
votes
0
answers
How to solve this problem using state elimination method?
asked
Apr 24
in
Theory of Computation
by
intgate
(
9
points)

20
views
theoryofcomputation
finiteautomata
0
votes
0
answers
self doubt on dfa
Minimum number of states for dfa accepting strings over {0,1} such that the kth bit from the right is 1 is 2^k where 2 is the number of alphabets(link:https://gateoverflow.in/63063/dfa). So according to this result, the number of states for the ... alphabets and k=2. But according to the link a minimal dfa with only 4 states could be found...then how is the result true?
asked
Apr 22
in
Theory of Computation
by
Deterministic
(
23
points)

24
views
theoryofcomputation
finiteautomata
0
votes
0
answers
GATE200634 Video Solution
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2006
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE2016242 Video Solution
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
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate20162
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE2017239 Video Solution
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$NFA whose transition table is given below: $\begin{array}{cccc}\hline \delta & \text{$\epsilon$} & \text{$a$} & \text{$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

16
views
gate20172
theoryofcomputation
finiteautomata
videosolution
0
votes
0
answers
GATE2017122 Video Solution
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finitestate automaton (DFA) accepting $L$ is ___________ .
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

4
views
gate20171
theoryofcomputation
finiteautomata
numericalanswers
minimalstateautomata
videosolution
0
votes
0
answers
GATE20012.5 Video Solution
Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have? $8$ $14$ $15$ $48$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

7
views
gate2001
theoryofcomputation
finiteautomata
minimalstateautomata
videosolution
0
votes
0
answers
GATE201041 Video Solution
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}$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate2010
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE19991.4 Video Solution
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate1999
theoryofcomputation
finiteautomata
easy
minimalstateautomata
videosolution
0
votes
0
answers
GATE201212 Video Solution
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

4
views
gate2012
finiteautomata
easy
theoryofcomputation
videosolution
0
votes
0
answers
GATE201948 Video Solution
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

8
views
gate2019
numericalanswers
theoryofcomputation
finiteautomata
minimalstateautomata
difficult
videosolution
0
votes
0
answers
GATE200849 Video Solution
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state) $\overset{Y}{\begin{array}{lll}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow$ $ ...
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

11
views
gate2008
normal
theoryofcomputation
finiteautomata
videosolution
0
votes
0
answers
GATE201142 Video Solution
Definition of a language $L$ with alphabet $\{a\}$ is given as following.$ L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$What is the minimum number of states needed in a DFA to recognize $L$? $k+1$ $n+1$ $2^{n+1}$ $2^{k+1}$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate2011
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE2017225 Video Solution
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$  $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left  w_{1} \right  = 2, \left  w_{2} \right \geq 3$} is ______________ .
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
theoryofcomputation
gate20172
finiteautomata
numericalanswers
minimalstateautomata
videosolution
0
votes
0
answers
GATE20011.6 Video Solution
Given an arbitrary nondeterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2001
finiteautomata
theoryofcomputation
easy
minimalstateautomata
videosolution
0
votes
0
answers
GATE2015152 Video Solution
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

3
views
gate20151
theoryofcomputation
finiteautomata
easy
numericalanswers
minimalstateautomata
videosolution
0
votes
0
answers
GATE2014136 Video Solution
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate20141
theoryofcomputation
regularexpressions
finiteautomata
easy
videosolution
0
votes
0
answers
GATE2015318 Video Solution
Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate20153
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE19982.5 Video Solution
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$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate1998
theoryofcomputation
finiteautomata
normal
minimalstateautomata
videosolution
0
votes
0
answers
GATE201333 Video Solution
Consider the DFA $A$ given below. Which of the following are FALSE? Complement of $L(A)$ is contextfree. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*) $ For the language accepted by $A, A$ is the minimal DFA. $A$ accepts all strings over $\{0, 1\}$ of length at least $2$. 1 and 3 only 2 and 4 only 2 and 3 only 3 and 4 only
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2013
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE200350 Video Solution
Consider the following deterministic finite state automaton $M$. Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $1$. The number of strings in $S$ that are accepted by $M$ is $1$ $5$ $7$ $8$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

8
views
gate2003
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE2005IT37 Video Solution
Consider the nondeterministic finite automaton (NFA) shown in the figure. State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ as the only accepting state be $L1$. Similarly, let the language accepted by the NFA with $Z$ ... statements about $L1$ and $L2$ is TRUE? $L1 = L2$ $L1 \subset L2$ $L2 \subset L1$ None of the above
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2005it
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE201246 Video Solution
Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed ...
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

7
views
gate2012
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE200355 Video Solution
Consider the NFA $M$ shown below. Let the language accepted by $M$ be $L$. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of $M$ to a nonaccepting state and by changing the nonaccepting states of $M$ to accepting states. Which ... statements is true? $L_1 = \{0,1\}^*L$ $L_1 = \{0,1\}^*$ $L_1 \subseteq L$ $L_1 = L$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

14
views
gate2003
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE19981.10 Video Solution
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\}$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

7
views
gate1998
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE2007IT50 Video Solution
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 :
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2007it
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE19962.23 Video Solution
Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

4
views
gate1996
theoryofcomputation
normal
finiteautomata
minimalstateautomata
videosolution
0
votes
0
answers
GATE19943.3 Video Solution
State True or False with one line explanation A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

8
views
gate1994
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE200852 Video Solution
Match the following NFAs with the regular expressions they correspond to: P Q R S $\epsilon + 0\left(01^*1+00\right)^*01^*$ $\epsilon + 0\left(10^*1+00\right)^*0$ $\epsilon + 0\left(10^*1+10\right)^*1$ $\epsilon + 0\left(10^*1+10\right)^*10^*$ $P2, Q1, R3, S4$ $P1, Q3, R2, S4$ $P1, Q2, R3, S4$ $P3, Q2, R1, S4$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

6
views
gate2008
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE200927 Video Solution
Given the following state table of an FSM with two states $A$ and $B$ ... length of an input string which will take the machine to the state $A=0,B=1$ with $output=1$. $3$ $4$ $5$ $6$
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

7
views
gate2009
theoryofcomputation
finiteautomata
normal
videosolution
0
votes
0
answers
GATE2015253 Video Solution
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
asked
Apr 18
in
Theory of Computation
by
admin
(
197
points)

5
views
gate20152
theoryofcomputation
finiteautomata
normal
numericalanswers
minimalstateautomata
videosolution
Page:
1
2
3
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Recent Posts
New GATEOverflow PDFs
Guidelines to users
Recent Blog Comments
Thanks, Can you tell me till when this might get...
8,677
questions
2,878
answers
13,799
comments
95,576
users