Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged minimal-state-automata
0
votes
1
answer
151
Finding minimum states in FA.
If it is asked for minimum states required in FA for some language, we can have both NFA and DFA, and NFA has lesser number of states but many books write that consider DFA as default. What to take into consideration in such case?NFA or DFA?
If it is asked for minimum states required in FA for some language, we can have both NFA and DFA, and NFA has lesser number of states but many books write that consider D...
parthsl
687
views
parthsl
asked
Jan 27, 2016
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
1
votes
2
answers
152
#Number of states in minimal DFA
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11. (a) 6 (b) 7 (c) 8 (d) 9
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11.(a) 6 (b) 7(c) 8 (d) 9
Pooja Palod
3.2k
views
Pooja Palod
asked
Jan 25, 2016
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
0
votes
1
answer
153
confusion in finding states in minimal DFA
number of states in the dfa which accepts the binary strings whose decimal equivalent is divisible by 5 ? since ∊ is not accepted as it doesn't have any decimal equivalent so initial state cannot be accepting state so to accept 0 (zero) there should be some other state than the initial state . so what will be the answer 5 or 6
number of states in the dfa which accepts the binary strings whose decimal equivalent is divisible by 5 ? since ∊ is not accepted as it doesn't have any decimal equ...
hkara657
576
views
hkara657
asked
Jan 24, 2016
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
0
votes
1
answer
154
TOC: DFA Minimization
Clear Image URL: http://postimg.org/image/ljcst3k0t/
Clear Image URL: http://postimg.org/image/ljcst3k0t/
Prasanna
746
views
Prasanna
asked
Jan 24, 2016
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
2
votes
2
answers
155
Minimum number of states in the DFA
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$ I draw the following DFA The minimum number of states is 4. The answer given is 8. How is it possible? Please explain.
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...
Utk
16.1k
views
Utk
asked
Jan 13, 2016
Theory of Computation
minimal-state-automata
finite-automata
theory-of-computation
+
–
0
votes
0
answers
156
Dfa
Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4 Can't we eliminate state q3? as q1 and q3 hav same inputs and output transition. I think it is same as a language having strings ending with 10. Right na?
Construct the minimal dfa that accept all binary numbers which have congruent to 2mod4Can't we eliminate state q3?as q1 and q3 hav same inputs and output transition.I thi...
khushtak
391
views
khushtak
asked
Jan 11, 2016
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
5
votes
2
answers
157
How to construct compound Automata ? and find the no of states in minimal FA ?
Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN . Also find no of states in its minimal FA
Construct Minimal FA that accept all binary strings ends with 01 AND length of string is EVEN .Also find no of states in its minimal FA
pC
2.7k
views
pC
asked
Jan 2, 2016
Theory of Computation
compound-automata
minimal-state-automata
+
–
3
votes
1
answer
158
dfa
Find minimal finitte automata for L1:L1 contains set of strings starting with 1010 and length of string is divisible by 4. L2:L2 contains set of strings starting woth 1010 and its equivalent decimal value divisible by 4
Find minimal finitte automata forL1:L1 contains set of strings starting with 1010 and length of string is divisible by 4.L2:L2 contains set of strings starting woth 1010 ...
Pooja Palod
1.0k
views
Pooja Palod
asked
Dec 23, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
1
votes
1
answer
159
Toc DFA
no of states for accepting €?
no of states for accepting €?
Amey
629
views
Amey
asked
Dec 22, 2015
Theory of Computation
minimal-state-automata
+
–
0
votes
1
answer
160
minimum no of states and final states
I solved both of these qs in a traditional way,by drawing nfa and then convert them to dfa..by tthis process ans shoulbe 4 and 2..but both of them are wrong..pls check..
I solved both of these qs in a traditional way,by drawing nfa and then convert them to dfa..by tthis process ans shoulbe 4 and 2..but both of them are wrong..pls check..
resuscitate
2.8k
views
resuscitate
asked
Dec 13, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
6
votes
2
answers
161
How to approach this type of question
The number of states in DFA which accepts a language such that each block of $4$ consecutive symbols of every string contain at least two $a's$ for $\Sigma =\{a,b\}$ is ___________. [if String length is less that $4$ then it must be accepted]
The number of states in DFA which accepts a language such that each block of $4$ consecutive symbols of every string contain at least two $a's$ for $\Sigma =\{a,b\}$ is _...
Akanksha Kesarwani
6.4k
views
Akanksha Kesarwani
asked
Dec 13, 2015
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
0
votes
1
answer
162
what is the minimum no of DFA states required to recognise below language?
L={a^nk , k>0 and n is an integer constant } In this question which constant should be changed , n or k while considering the DFA since then it can be either n+1 or k+1 ?
L={a^nk , k>0 and n is an integer constant }In this question which constant should be changed , n or k while considering the DFA since then it can be either n+1 or k+1 ?
radha gogia
2.0k
views
radha gogia
asked
Nov 17, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
1
votes
2
answers
163
number of states required to construct dfa accepting language L = (ab+aba)*
number of states required to construct dfa accepting languages L = (ab union aba)* alphabet = {a,b} is atleast?? my view: for intersection of 2 reg langs we take cartesian product construct dfa then we mininise it ... ... produce least no.for required states but for above question like (ab+aba)* what should i do to solve ?
number of states required to construct dfa accepting languages L = (ab union aba)* alphabet = {a,b} is atleast??my view:for intersection of 2 reg langs we take cartesian...
Ravi Raaja
3.1k
views
Ravi Raaja
asked
Nov 16, 2015
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
3
votes
2
answers
164
Binary Number when interpreted as decimal mod 12
What are the Number of states in minimum DFA that accepts Binary strings when interpreted as decimal mod 12 give 0 as remainder.Also give DFA.
What are the Number of states in minimum DFA that accepts Binary strings when interpreted as decimal mod 12 give 0 as remainder.Also give DFA.
Himanshu1
1.4k
views
Himanshu1
asked
Nov 2, 2015
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
21
votes
2
answers
165
GATE CSE 1997 | Question: 70
Following is a state table for time finite state machine. ... . For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).
Following is a state table for time finite state machine.$$\begin{array}{|l|ll|}\hline \textbf{Present State} & \textbf{Next State Output} \\ & \textbf{Input- 0} & \t...
go_editor
7.7k
views
go_editor
asked
Oct 14, 2015
Theory of Computation
gate1997
theory-of-computation
minimal-state-automata
descriptive
+
–
2
votes
1
answer
166
Non-deterministic Finite Machine
Let M be a Non-deterministic Finite Machine. Let G be the Regular Grammar obtained from M. Which is True? (a) G will always be unambiguous (b) G will always be ambiguous (c) G may be ambiguous (d) None of the above
Let M be a Non-deterministic Finite Machine. Let G be the Regular Grammar obtained from M. Which is True?(a) G will always be unambiguous(b) G will always be ambiguous(c)...
Mojo-Jojo
1.6k
views
Mojo-Jojo
asked
Sep 28, 2015
Theory of Computation
finite-automata
regular-expression
minimal-state-automata
+
–
0
votes
0
answers
167
states required for L* using Thompson's Construction?
Q. If machine M is recognizing L with n states. Then M' recognizing L* construed using Thompson's Construction will have ___ states. a) n b) n+1 c) n+2 d) n-1 I know that we use Thompson's construction while ... "We need one extra state to eliminate the e-moves" . How can this be done? Can somebody plz explain. Thanks.
Q. If machine M is recognizing L with n states. Then M' recognizing L* construed using Thompson's Construction will have ___ states.a) nb) n+1c) n+2d) n-1I know that we u...
Tushar Shinde
1.6k
views
Tushar Shinde
asked
Sep 17, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
2
votes
2
answers
168
NFA to DFA Conversion
If NFA has n states, then its DFA can have______states in worst case.
If NFA has n states, then its DFA can have______states in worst case.
anonymous
1.8k
views
anonymous
asked
Sep 9, 2015
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
2
votes
2
answers
169
Let Σ= {a}, assume language, L= { a^(2012.K) / K> 0}, what is minimum number of states needed in a DFA to recognize L
Let Σ= {a}, assume language, L= { a^(2012.K) / K 0}, what is minimum number of states needed in a DFA to recognize L
Anurag_s
3.2k
views
Anurag_s
asked
Aug 15, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
1
votes
1
answer
170
Please post the DFA for the language.
What are the number of final states in minimal DFA, where $\Sigma = \{a,b\}$, if every string starts with "aa" and length of string is not congruent to 0 mod 4? 7 6 3 5
What are the number of final states in minimal DFA, where $\Sigma = \{a,b\}$, if every string starts with "aa" and length of string is not congruent to 0 mod 4?7635
Aditya
2.0k
views
Aditya
asked
Jul 30, 2015
Theory of Computation
minimal-state-automata
+
–
4
votes
5
answers
171
minimal DFA
The minimal state DFA, accepting all strings over the alphabet {0,1} where the nth symbol in every string from the right end is a 1, has a) 2n states b) 2n-1 states c) 2n+1 states d) None of the above
The minimal state DFA, accepting all strings over the alphabet {0,1} where the nth symbol in every string from the right end is a 1, hasa) 2n states b) 2n-1 states c) 2n...
sumit kumar
5.3k
views
sumit kumar
asked
Jun 22, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
3
votes
2
answers
172
no of states in minimal dfa
Q no. of states in minimal DFA built for: accepts all strings over the alphabet {0,1} interpreted as a binary number is congruent to zero modulo n has a)n states b)n-1 states c)n+1 states d)None of the above basically, i didn't get what they are trying to say in this question?(correct answer is option A)
Qno. of states in minimal DFA built for:accepts all strings over the alphabet {0,1} interpreted as a binary number is congruent to zero modulo n hasa)n statesb)n-1 states...
sumit kumar
4.5k
views
sumit kumar
asked
Jun 22, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
7
votes
2
answers
173
the possible no of dfa with three states
Q The possible no of dfa with three states X,Y and Z, where X being always initial state for the DFA over the alphabet {0,1} a)5830 b)5831 c)5832 d)5932 correct answer is option C,but what is the systematic way to get it??
QThe possible no of dfa with three states X,Y and Z, where X being always initial state for the DFA over the alphabet {0,1}a)5830b)5831c)5832d)5932correct answer is optio...
sumit kumar
7.8k
views
sumit kumar
asked
Jun 22, 2015
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
2
votes
2
answers
174
draw DFA in 3 states
well, according to a question for matching minimal state dfa to regular expression,following match is given to be correct,but i don't find that correct.can you guys please try to prove it's correctness or wrongness?? (a+b)*ab*ab* ---- can be drawn in 3 states(given correct) but how???
well, according to a question for matching minimal state dfa to regular expression,following match is given to be correct,but i don't find that correct.can you guys pleas...
sumit kumar
702
views
sumit kumar
asked
Jun 22, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
0
votes
1
answer
175
Minimization of FA
We define a removable state as a state such that if we erase the state itself & the edges that come out of it, what results is a perfectly good looking FA. (i) Give an example of an FA that contains a removable state. (ii) Show that if we erase a removable state the language defined by the reduced FA is exactly the same as the language defined by the old FA.
We define a removable state as a state such that if we erase the state itself & the edges that come out of it, what results is a perfectly good looking FA.(i) Give an exa...
Aakanchha
1.4k
views
Aakanchha
asked
May 25, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
55
votes
5
answers
176
GATE CSE 2015 Set 3 | Question: 18
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$
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 recogni...
go_editor
16.9k
views
go_editor
asked
Feb 14, 2015
Theory of Computation
gatecse-2015-set3
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
65
votes
12
answers
177
GATE CSE 2015 Set 1 | Question: 52
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_____________.
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_____________.
makhdoom ghaya
17.0k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
finite-automata
easy
numerical-answers
minimal-state-automata
+
–
36
votes
6
answers
178
GATE CSE 2015 Set 2 | Question: 53
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
go_editor
15.5k
views
go_editor
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set2
theory-of-computation
finite-automata
normal
numerical-answers
minimal-state-automata
+
–
4
votes
3
answers
179
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?
What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?A. 8B. 9C. 6D. None
Vikrant Singh
3.2k
views
Vikrant Singh
asked
Jan 25, 2015
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
30
votes
5
answers
180
GATE IT 2008 | Question: 6
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true? $m \leq 2^n$ $n \leq m$ $M$ has one accept state $m = 2^n$
Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?$m \leq 2^n$$...
Ishrat Jahan
10.7k
views
Ishrat Jahan
asked
Oct 27, 2014
Theory of Computation
gateit-2008
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
Page:
« prev
1
2
3
4
5
6
7
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register