menu
Recent questions tagged finite-automata
Login
Register
My account
Edit my Profile
Private messages
My favorites
Register
Recent questions tagged finite-automata
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Blogs
Previous Year
Exams
Recent questions tagged finite-automata
1
vote
0
answers
19
views
#Theory of computation(DFA)
Construct DFA with ∑ = {0, 1} accepts the strings with an even number of 0's followed by single 1.
Urvesh
asked
in
Theory of Computation
Aug 24
by
Urvesh
9
points
19
views
finite-automata
0
votes
0
answers
32
views
automata theory & formal language
Instructions: Create an FA for the RE ((0+1) (0+1))* + ((0+1) 0
arce
asked
in
Algorithms
Aug 24
by
arce
5
points
32
views
finite-automata
0
votes
0
answers
173
views
Countability in toc
Hi What is best resource and Where to study countability topic in toc?
ykrishnay
asked
in
Theory of Computation
Aug 21
by
ykrishnay
103
points
173
views
self-doubt
finite-automata
toc-languages
theory-of-computation
0
votes
0
answers
31
views
How to design Turing machine for addition of 2 binary numbers
ykrishnay
asked
in
Theory of Computation
Aug 18
by
ykrishnay
103
points
31
views
turing-machine
self-doubt
compiler-design
toc-languages
finite-automata
0
votes
0
answers
34
views
Self doubt.
What are the differences between a dead state and a trap state?
raja11sep
asked
in
Theory of Computation
Jun 30
by
raja11sep
5
points
34
views
self-doubt
finite-automata
0
votes
0
answers
40
views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
promise
asked
in
Theory of Computation
Jun 8
by
promise
5
points
40
views
nfa-dfa
regular-languages
regular-grammar
finite-automata
0
votes
1
answer
27
views
while making compound automata do we have to include the dead states too in the cartesian product ?[self doubt]
rythmrana
asked
in
Theory of Computation
May 16
by
rythmrana
5
points
27
views
finite-automata
0
votes
0
answers
36
views
AppliedGate lecture example
What is the NFA that does not accept strings ending “101” ?
shri385
asked
in
Theory of Computation
Apr 7
by
shri385
5
points
36
views
nfa-dfa
toc-languages
finite-automata
5
votes
3
answers
1.2k
views
GATE CSE 2021 Set 2 | Question: 9 | Video Solution
Arjun
asked
in
Theory of Computation
Feb 18
by
Arjun
1.5k
points
1.2k
views
gate2021-cse-set2
theory-of-computation
finite-automata
regular-languages
2
votes
2
answers
739
views
GATE CSE 2021 Set 2 | Question: 17 | Video Solution
Arjun
asked
in
Theory of Computation
Feb 18
by
Arjun
1.5k
points
739
views
gate2021-cse-set2
numerical-answers
theory-of-computation
finite-automata
2
votes
2
answers
662
views
GATE CSE 2021 Set 2 | Question: 28 | Video Solution
Arjun
asked
in
Theory of Computation
Feb 18
by
Arjun
1.5k
points
662
views
gate2021-cse-set2
theory-of-computation
finite-automata
0
votes
1
answer
443
views
GATE CSE 2021 Set 1 | Question: 38 | Video Solution
Arjun
asked
in
Theory of Computation
Feb 18
by
Arjun
1.5k
points
443
views
gate2021-cse-set1
theory-of-computation
finite-automata
1
vote
1
answer
44
views
Made easy test series
Can anyone draw the DFA’s for the question mentioned?
phaneendrababu
asked
in
Theory of Computation
Jan 22
by
phaneendrababu
11
points
44
views
finite-automata
0
votes
0
answers
20
views
My college homework
1) Let ∑ = {D , L}. Find a DFA that accepts Password (P) with the following conditions: - | P | ≥ 4 - P begins with a letter and ends with a letter. - P contains at least one digit. 2) Let ∑ = { 0..9 , ... the following DFA that has access to the laboratories of company controlled. The employee number becomes read as a binary number. Which employee numbers are accepted.
MotasemMobayyed
asked
in
Theory of Computation
Dec 29, 2020
by
MotasemMobayyed
5
points
20
views
finite-automata
0
votes
1
answer
53
views
Theory of automata
Convert the Following DFA to Regular Expression using GNFA.
M.hamza
asked
in
Theory of Computation
Dec 26, 2020
by
M.hamza
5
points
53
views
finite-automata
toc-languages
0
votes
0
answers
21
views
Theory of Automata
Consider the following regular expression: (a+b) a) Convert the given regular expression to NFA-ε. b) Convert the NFA-ε obtained in a) to NFA.
Ehtisham
asked
in
Others
Dec 16, 2020
by
Ehtisham
5
points
21
views
finite-automata
0
votes
0
answers
59
views
Self made question on Regular expression, Is my answer right?
ijnuhb
asked
in
Theory of Computation
Dec 9, 2020
by
ijnuhb
751
points
59
views
finite-automata
0
votes
2
answers
99
views
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
rish1602
asked
in
Theory of Computation
Oct 24, 2020
by
rish1602
9
points
99
views
toc-languages
finite-automata
0
votes
0
answers
15
views
Self Doubt Theory of Computation-How to distinguish when to use cross product, concatenation or Union in DFA?
the_dalela
asked
in
Theory of Computation
Oct 2, 2020
by
the_dalela
5
points
15
views
finite-automata
0
votes
1
answer
130
views
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 _____.
Animesh Sinha
asked
in
Digital Logic
Aug 29, 2020
by
Animesh Sinha
25
points
130
views
gradeup
finite-automata
digital-logic
0
votes
2
answers
50
views
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.
abhish1mishra
asked
in
Compiler Design
Aug 25, 2020
by
abhish1mishra
5
points
50
views
theory-of-computation
finite-automata
theory-of-computation
0
votes
1
answer
44
views
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.
abhijeet at
asked
in
Theory of Computation
Aug 18, 2020
by
abhijeet at
9
points
44
views
theory-of-computation
finite-automata
0
votes
0
answers
49
views
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?
aryashah2k
asked
in
Theory of Computation
Aug 1, 2020
by
aryashah2k
2
points
49
views
finite-automata
theory-of-computation
automata
dfadesign
0
votes
0
answers
62
views
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
aryashah2k
asked
in
Theory of Computation
Jul 24, 2020
by
aryashah2k
2
points
62
views
theory-of-computation
finite-automata
dfadesign
automata
0
votes
0
answers
37
views
Gate-2008-IT-2008-32
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
prajjwalsingh_11
asked
in
Theory of Computation
Jul 18, 2020
by
prajjwalsingh_11
15
points
37
views
theory-of-computation
finite-automata
regular-expressions
ardens-theorem
1
vote
0
answers
107
views
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}?
Shreya2002
asked
in
Theory of Computation
May 16, 2020
by
Shreya2002
9
points
107
views
theory-of-computation
finite-automata
0
votes
0
answers
31
views
How to solve this problem using state elimination method?
intgate
asked
in
Theory of Computation
Apr 24, 2020
by
intgate
9
points
31
views
theory-of-computation
finite-automata
0
votes
0
answers
34
views
self doubt on dfa
Minimum number of states for dfa accepting strings over {0,1} such that the k-th 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?
Deterministic
asked
in
Theory of Computation
Apr 22, 2020
by
Deterministic
31
points
34
views
theory-of-computation
finite-automata
0
votes
0
answers
15
views
GATE2006-34 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$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
15
views
gate2006
theory-of-computation
finite-automata
normal
minimal-state-automata
video-solution
0
votes
0
answers
14
views
GATE2016-2-42 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
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
14
views
gate2016-2
theory-of-computation
finite-automata
normal
video-solution
0
votes
0
answers
26
views
GATE2017-2-39 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}{|c|c|c|c|}\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 \}$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
26
views
gate2017-2
theory-of-computation
finite-automata
video-solution
0
votes
0
answers
13
views
GATE2017-1-22 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 finite-state automaton (DFA) accepting $L$ is ___________ .
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
13
views
gate2017-1
theory-of-computation
finite-automata
numerical-answers
minimal-state-automata
video-solution
0
votes
0
answers
20
views
GATE2001-2.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$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
20
views
gate2001
theory-of-computation
finite-automata
minimal-state-automata
video-solution
0
votes
0
answers
15
views
GATE2010-41 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 non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
15
views
gate2010
theory-of-computation
finite-automata
normal
minimal-state-automata
video-solution
0
votes
0
answers
17
views
GATE1999-1.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
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
17
views
gate1999
theory-of-computation
finite-automata
easy
minimal-state-automata
video-solution
0
votes
0
answers
13
views
GATE2012-12 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\}$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
13
views
gate2012
finite-automata
easy
theory-of-computation
video-solution
0
votes
0
answers
17
views
GATE2019-48 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 _______
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
17
views
gate2019
numerical-answers
theory-of-computation
finite-automata
minimal-state-automata
difficult
video-solution
0
votes
0
answers
21
views
GATE2008-49 Video Solution
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state) $\overset{Y}{\begin{array}{|l|l|l|}\hline \text{} & \textbf{a} & \textbf{b} \\\hline \text{$\rightarrow$ $ ...
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
21
views
gate2008
normal
theory-of-computation
finite-automata
video-solution
0
votes
0
answers
12
views
GATE2011-42 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}$
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
12
views
gate2011
theory-of-computation
finite-automata
normal
minimal-state-automata
video-solution
0
votes
0
answers
16
views
GATE2017-2-25 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 ______________ .
admin
asked
in
Theory of Computation
Apr 18, 2020
by
admin
581
points
16
views
theory-of-computation
gate2017-2
finite-automata
numerical-answers
minimal-state-automata
video-solution
Page:
1
2
3
4
next »
Ask
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
No Recent Blog Comments
Search GATE CSE Doubts