Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Some useful problems
Recent questions tagged finite-automata
46
votes
7
answers
1021
GATE CSE 2009 | Question: 41
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$.
Kathleen
asked
in
Theory of Computation
Sep 22, 2014
by
Kathleen
21.0k
views
gatecse-2009
theory-of-computation
finite-automata
easy
42
votes
6
answers
1022
GATE CSE 2009 | Question: 27
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$
Kathleen
asked
in
Theory of Computation
Sep 22, 2014
by
Kathleen
12.7k
views
gatecse-2009
theory-of-computation
finite-automata
normal
93
votes
8
answers
1023
GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
Rucha Shelke
asked
in
Theory of Computation
Sep 22, 2014
by
Rucha Shelke
34.1k
views
gatecse-2006
theory-of-computation
finite-automata
normal
minimal-state-automata
43
votes
6
answers
1024
GATE CSE 2007 | Question: 74
Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression $b^*ab^*ab^*ab^*$ $(a + b)^*$ $b^*a(a+b)^*$ $b^*ab^*ab^*$
Kathleen
asked
in
Theory of Computation
Sep 21, 2014
by
Kathleen
13.3k
views
gatecse-2007
theory-of-computation
finite-automata
normal
32
votes
4
answers
1025
GATE CSE 2007 | Question: 29
A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has $15$ states $11$ states $10$ states $9$ states
Kathleen
asked
in
Theory of Computation
Sep 21, 2014
by
Kathleen
11.5k
views
gatecse-2007
theory-of-computation
finite-automata
normal
minimal-state-automata
38
votes
4
answers
1026
GATE CSE 2004 | Question: 86
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$ odd and even even and odd divisible by $2$ and $3$
Kathleen
asked
in
Theory of Computation
Sep 18, 2014
by
Kathleen
8.3k
views
gatecse-2004
theory-of-computation
finite-automata
easy
45
votes
5
answers
1027
GATE CSE 2003 | Question: 55
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 non-accepting state and by changing the non-accepting 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$
Kathleen
asked
in
Theory of Computation
Sep 17, 2014
by
Kathleen
14.3k
views
gatecse-2003
theory-of-computation
finite-automata
normal
61
votes
7
answers
1028
GATE CSE 2003 | Question: 50
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$
Kathleen
asked
in
Theory of Computation
Sep 17, 2014
by
Kathleen
14.9k
views
gatecse-2003
theory-of-computation
finite-automata
normal
25
votes
1
answer
1029
GATE CSE 2002 | Question: 21
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$ Give an NFA for this purpose Give a DFA for this purpose
Kathleen
asked
in
Theory of Computation
Sep 15, 2014
by
Kathleen
4.2k
views
gatecse-2002
theory-of-computation
finite-automata
normal
descriptive
26
votes
3
answers
1030
GATE CSE 2002 | Question: 2.13
The smallest finite automaton which accepts the language $\{x \mid$ length of $x$ is divisible by $3\}$ has $2$ states $3$ states $4$ states $5$ states
Kathleen
asked
in
Theory of Computation
Sep 15, 2014
by
Kathleen
7.9k
views
gatecse-2002
theory-of-computation
normal
finite-automata
minimal-state-automata
40
votes
3
answers
1031
GATE CSE 2002 | Question: 2.5
The finite state machine described by the following state diagram with $A$ as starting state, where an arc label is $x/y,$ and $x$ stands for $1$-bit input and $y$ stands for $2$-bit output outputs the sum of the present and the ... the input outputs $01$ whenever the input sequence contains $11$ outputs $00$ whenever the input sequence contains $10$ none of the above
Kathleen
asked
in
Theory of Computation
Sep 15, 2014
by
Kathleen
11.2k
views
gatecse-2002
theory-of-computation
normal
finite-automata
36
votes
2
answers
1032
GATE CSE 2001 | Question: 5
Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
5.3k
views
gatecse-2001
theory-of-computation
easy
descriptive
finite-automata
normal
41
votes
4
answers
1033
GATE CSE 2001 | Question: 2.5
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$
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
18.5k
views
gatecse-2001
theory-of-computation
finite-automata
minimal-state-automata
29
votes
3
answers
1034
GATE CSE 2001 | Question: 1.6
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
15.8k
views
gatecse-2001
finite-automata
theory-of-computation
easy
minimal-state-automata
40
votes
9
answers
1035
GATE CSE 1991 | Question: 17,b
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?
Kathleen
asked
in
Theory of Computation
Sep 12, 2014
by
Kathleen
13.6k
views
gate1991
theory-of-computation
finite-automata
normal
descriptive
50
votes
11
answers
1036
GATE CSE 2008 | Question: 52
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^*$ $P-2, Q-1, R-3, S-4$ $P-1, Q-3, R-2, S-4$ $P-1, Q-2, R-3, S-4$ $P-3, Q-2, R-1, S-4$
Kathleen
asked
in
Theory of Computation
Sep 12, 2014
by
Kathleen
12.6k
views
gatecse-2008
theory-of-computation
finite-automata
normal
67
votes
4
answers
1037
GATE CSE 2008 | Question: 49
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ ...
Kathleen
asked
in
Theory of Computation
Sep 12, 2014
by
Kathleen
14.6k
views
gatecse-2008
normal
theory-of-computation
finite-automata
3
votes
1
answer
1038
Find n(K) where K is the size of string that a DFA accepts.
Subject: Finite Automata Topic: DFA Q) Can anyone explain me how i can find the no of strings of length k words that is accepted by a given DFA. Do post the resources which can be helpful to understand this concept.
nishu_gate
asked
in
Theory of Computation
Sep 10, 2014
by
nishu_gate
923
views
theory-of-computation
finite-automata
71
votes
14
answers
1039
GATE CSE 2012 | Question: 12
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\}$
gatecse
asked
in
Theory of Computation
Aug 5, 2014
by
gatecse
19.1k
views
gatecse-2012
finite-automata
easy
theory-of-computation
Page:
« prev
1
...
30
31
32
33
34
35
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged finite-automata
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...