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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions tagged finiteautomata
Some useful problems
0
votes
0
answers
1
what is the regular expression and design dfa and nfa for arthimatic expression
asked
May 13
in
Theory of Computation
by
doaa
(
31
points)

38
views
finiteautomata
theoryofcomputation
regularexpressions
dfa
nfa
0
votes
0
answers
2
FA to Regular Expression: when no two a's and no two b's should come together
asked
May 9
in
Theory of Computation
by
surbhijain93
(
31
points)

64
views
theoryofcomputation
regularexpressions
finiteautomata
0
votes
2
answers
3
No of states in Minimal DFA
Ques: Let ∑= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8)? *[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].
asked
May 8
in
Theory of Computation
by
kislaya Pant
(
41
points)

62
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
+1
vote
1
answer
4
Minimal Final States in DFA
Ques: What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4).
asked
May 8
in
Theory of Computation
by
kislaya Pant
(
41
points)

52
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
1
answer
5
Test Series
If there are Q states in NFA, DFA should have at max $2^{Q}$ states. Keeping this thing in mind I answered the question but it went wrong. Please if anyone can give the correct solution.
asked
May 6
in
Theory of Computation
by
Subham Nagar
(
497
points)

62
views
testseries
finiteautomata
theoryofcomputation
0
votes
1
answer
6
Automata (How to create DFA for the language)
asked
May 6
in
Theory of Computation
by
kislaya Pant
(
41
points)

44
views
theoryofcomputation
minimalstateautomata
finiteautomata
+2
votes
2
answers
7
ISRO201826
The $FSM$ (Finite State Machine) machine pictured in the figure above Complements a given bit pattern Finds $2's$ complement of a given bit pattern Increments a given bit pattern by $1$ Changes the sign bit
asked
Apr 22
in
Theory of Computation
by
Arjun
Veteran
(
342k
points)

777
views
isro2018
finiteautomata
theoryofcomputation
mooremealymachine
+1
vote
1
answer
8
Number of States in FA
Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted?
asked
Apr 8
in
Theory of Computation
by
smsubham
Loyal
(
6k
points)

102
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
0
answers
9
Worst Case in NFA to DFA Conversion
Can you give an example of NFA which has n states and its corresponding DFA has 2^n states?
asked
Apr 8
in
Theory of Computation
by
smsubham
Loyal
(
6k
points)

59
views
theoryofcomputation
nfa
finiteautomata
dfa
numberofstates
+1
vote
1
answer
10
#toc #peterlinz #nfa
Also is this nfa possible with less than three states??
asked
Apr 7
in
Theory of Computation
by
meghna
(
407
points)

77
views
finiteautomata
nfa
theoryofcomputation
+1
vote
2
answers
11
Regular Grammars
$S\rightarrow AB$ $A\rightarrow a$ $B\rightarrow b$ The language generated by the above grammar is ab and since we can give a FA for the language then it must be a regular language.Now,since the given grammar generates a regular language then it must be a regular ... but again it is not in the form of TYPE 3 or regular grammar,then how to identify if the grammar is regular or not?
asked
Apr 6
in
Theory of Computation
by
Sourav_35
(
79
points)

37
views
regulargrammar
theoryofcomputation
finiteautomata
+2
votes
1
answer
12
Time complexity to minimize Finite Automata
asked
Mar 27
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
5.4k
points)

81
views
theoryofcomputation
finiteautomata
dfa
nfa
0
votes
2
answers
13
finite automata
Draw the DFA for (a*b +b*a)
asked
Mar 17
in
Theory of Computation
by
varunraj
Junior
(
667
points)

103
views
theoryofcomputation
dfa
finiteautomata
+2
votes
1
answer
14
#TOC Doubt  Regular expressions
Part A: Given : (bab*ab*)* How can it be interpreted as: 1.((b+ab*)ab*)* 2.(b+(ab*ab*))* 3.((b+a)b*ab*)* Part B: 1.What will be its NFA ? 2.Can we draw a direct MINIMAL DFA for such questions?
asked
Mar 13
in
Theory of Computation
by
ashishgateashish
(
93
points)

118
views
regularexpressions
finiteautomata
nfa
dfa
theoryofcomputation
+1
vote
0
answers
15
Dfa to regex
please verify the regex
asked
Mar 12
in
Theory of Computation
by
Mk Utkarsh
Boss
(
12.3k
points)

48
views
theoryofcomputation
finiteautomata
regularexpressions
+1
vote
1
answer
16
Automata
If $L1$ is regular language and $L2$ is unknown language then what can we say about $L1L2$. Will it be regular or not? I think it will be regular because even if $L2$ is not regular then still (Regular  not Regular) will result in Regular, according to the properties of set ... from The given set will not change the set. I want to know if I am right and if I am not then what's the error?
asked
Mar 10
in
Theory of Computation
by
hrcule
(
141
points)

51
views
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
0
answers
17
Peter linz exercise 2.1
$\sum = \left \{ a,b \right \}$ Is it possible to create DFA for given language with less than 10 states? L = $\left \{ w: \left  w \right  mod 3 = 0, \left w \right  \neq 6 \right \}$
asked
Mar 4
in
Theory of Computation
by
Mk Utkarsh
Boss
(
12.3k
points)

60
views
theoryofcomputation
finiteautomata
+1
vote
0
answers
18
Regular Expression
What is the regular expression of $L = \{ s \in L$ $i$ = no of $1$ in string $s$ $j$ = no of $0$ in string $s$ $i+j$ is odd $\}$ ???
asked
Mar 4
in
Theory of Computation
by
Dharmesh Gusai
(
19
points)

75
views
regularexpressions
theoryofcomputation
finiteautomata
regularlanguages
+1
vote
1
answer
19
Language accepted by given NFA
Language accepted by following NFA and number of states in DFA accepting that Language are: $\{a^nn=2k,kϵN\}$ and 2 $\{a^{2n}n=2k,kϵN\}$ and 2 $\{a^nn=2k,kϵ N\}$ and 3 $\{a^{2n}n=2k,kϵ N\}$ and 3
asked
Mar 2
in
Theory of Computation
by
GateAspirant999
Active
(
2.5k
points)

52
views
finiteautomata
nondeterminism
theoryofcomputation
+2
votes
1
answer
20
Regular language Prefix
Given FSA for language L, how to find FSA that accepts all prefixes of L? Acc to below mentioned link "We can construct a DFA to decide Prefix(L) by taking the DFA for L and marking all states from which an accept state is reachable ... states from which an accept state is reachable as accept states, then eventually all states would turn to final states.Am I right?
asked
Mar 2
in
Theory of Computation
by
Mamta Satywali
Active
(
2.2k
points)

57
views
theoryofcomputation
regularlanguages
finiteautomata
+1
vote
2
answers
21
NFAE to DFA conversion. (which is the correct solution?)
asked
Feb 27
in
Theory of Computation
by
ashishgateashish
(
93
points)

300
views
theoryofcomputation
nfa
finiteautomata
dfa
numberofstates
0
votes
0
answers
22
Minimization of FSM
Is minimization of Finite State Machine(FSM) based on Dynamic Programming(DP) paradigm ? If yes , then what should be the optimal substructure and overlapping subproblems ?
asked
Feb 25
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
5.4k
points)

62
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
23
TOC *** test series FA
question seems to be easy. but could not understand the solution
asked
Feb 11
in
Theory of Computation
by
Moin Mukhtar
(
253
points)

113
views
theoryofcomputation
finiteautomata
testseries
+2
votes
1
answer
24
Regular Language
Let $L\mid$ be a regular language and $L_1 = \{x\mid\text{there exist y}\mid \text{so that xy} \in L \text{ and} \mid x \mid = 2 \mid y\mid \mid \}$ $L_2 = \{x\mid\text{there exist y}\mid \text{so that yx} \in L \text{ and} \mid x ... is regular but $L_2$ is not. $L_2$ is regular but $L_1$ is not. Both $L_1$ and $L_2$ are regular. Both $L_1$ and $L_2$ are not regular.
asked
Feb 2
in
Theory of Computation
by
vijay_jr
Active
(
1.1k
points)

75
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
0
answers
25
#TOC Doubt
L = anbm / n,m>=1 What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same values!?
asked
Jan 30
in
Theory of Computation
by
iarnav
Loyal
(
6.9k
points)

44
views
theoryofcomputation
finiteautomata
regularexpressions
regulargrammar
+2
votes
2
answers
26
How many states in finite automata for the expression L={a^n, where n is a finite number}.
asked
Jan 28
in
Theory of Computation
by
Jayant Isswani
(
67
points)

115
views
finiteautomata
minimalstateautomata
theoryofcomputation
+2
votes
1
answer
27
regular expressions
Answer is c. but i think it should be b as r1 = (0+1)* = r2=r3. please correct me if i m wrong
asked
Jan 11
in
Theory of Computation
by
amIndian
(
71
points)

91
views
theoryofcomputation
regularexpressions
regularlanguages
finiteautomata
+3
votes
1
answer
28
automata
How many states in dfa of X= { (a+b)* where no of a is divisible by 4 and 8}
asked
Jan 9
in
Theory of Computation
by
raviyogi
Active
(
2.5k
points)

98
views
theoryofcomputation
finiteautomata
dfa
+1
vote
1
answer
29
Gateforum test series
Find the DFA corresponding to the given regular expression (0+11(01)*1)*
asked
Jan 3
in
Theory of Computation
by
Mk Utkarsh
Boss
(
12.3k
points)

99
views
gateforumtestseries
theoryofcomputation
finiteautomata
+2
votes
2
answers
30
#Strings DFA
$ L\ =\ \{\ a^mb^{2n}c^{3n}d^p\ \ m,n\ >=1\ ,\ p\ >\ m\} \\Find\ the\ number\ of\ strings\ of\ length\ <=\ 13$
asked
Dec 31, 2017
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
7.8k
points)

106
views
theoryofcomputation
dfa
finiteautomata
numberofstates
Page:
1
2
3
4
5
6
...
13
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
Recent Posts
Selected for M.Tech Computer Science in University of Hyderabad
Gate 2019 suggestion
IIIT Hyderabad interview Experience  2017
Experts please enlighten me!
IIT Gandhinagar MTECH CSE Interview Experience  May 8, 2018
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
That is google form link. You may try ...
As far as I know, the institute is new and ...
Link
1. One offer per round according to your ...
ok . then also answer would remain same , if your ...
35,458
questions
42,704
answers
121,329
comments
42,105
users