Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged minimal-state-automata
0
votes
1
answer
61
GATE CS Mock 2018 (Set -2)
Let δ denote the transition function and α denoted the extended transition function of the ε-NFA whose transition table is given below: Which of the following option is correct? A) α (q1,aba) is {q0, q2} B) null reachable states are {q0, q1, q2}B C) α (q3,bab) is {q0, q1, q2, q3} D) None of these
Let δ denote the transition function and α denoted the extended transition function of the ε-NFA whose transition table is given below:Which of the following option is...
Nikhil Patil
1.5k
views
Nikhil Patil
asked
Jun 11, 2018
Theory of Computation
usergate2018
usermod
finite-automata
minimal-state-automata
+
–
0
votes
2
answers
62
Toc DFA
Prince Sindhiya
431
views
Prince Sindhiya
asked
Jun 6, 2018
Theory of Computation
minimal-state-automata
+
–
1
votes
2
answers
63
Toc dfa
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
Shivani gaikawad
960
views
Shivani gaikawad
asked
Jun 5, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
2
votes
2
answers
64
Toc NFa
Shivani gaikawad
297
views
Shivani gaikawad
asked
Jun 5, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
0
votes
2
answers
65
Toc DFA
The minimum number of state in the DFA for the language $L = \{ w \mid w \in \{a,b\}^* \text{ w has exactly two a's and at least two b's} \}$ is $9$ $10$ $16$ None
The minimum number of state in the DFA for the language $L = \{ w \mid w \in \{a,b\}^* \text{ w has exactly two a's and at least two b's} \}$ is $9$$10$$16$None
Shivani gaikawad
464
views
Shivani gaikawad
asked
Jun 5, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
0
votes
3
answers
66
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].
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 ...
kislaya Pant
3.2k
views
kislaya Pant
asked
May 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
1
answer
67
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).
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)....
kislaya Pant
1.1k
views
kislaya Pant
asked
May 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
0
votes
1
answer
68
Automata (How to create DFA for the language)
Ques:- How to create minimal DFA over w where w belongs to (a,b)* such 2nd symbol from RHS should be 'a'?
Ques:- How to create minimal DFA over w where w belongs to (a,b)* such 2nd symbol from RHS should be 'a'?
kislaya Pant
1.1k
views
kislaya Pant
asked
May 5, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
1
votes
1
answer
69
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?
Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted?
smsubham
2.7k
views
smsubham
asked
Apr 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
0
answers
70
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 ?
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...
ankitgupta.1729
578
views
ankitgupta.1729
asked
Feb 25, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
24
votes
2
answers
71
GATE CSE 2018 | Question: 6
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true? $k \geq 2^n$ $k \geq n$ $k \leq n^2$ $k \leq 2^n$
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true?$k \geq 2^n...
gatecse
10.4k
views
gatecse
asked
Feb 14, 2018
Theory of Computation
gatecse-2018
theory-of-computation
minimal-state-automata
normal
1-mark
+
–
0
votes
1
answer
72
Minimal DFA
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____ My ans : 4 states given ans : 5 states
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____My ans : 4 states given ans : 5 states
Anjan
1.9k
views
Anjan
asked
Jan 31, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
2
votes
2
answers
73
How many states in finite automata for the expression L={a^n, where n is a finite number}.
I know that for L={a^n, n>=0}, there would be 2 states in DFA because there is no restriction on the value of n. However, what would be the no of states when n is restricted to a finite value, such as 1000 or 10000? And how feasible would it be to construct such a DFA?
I know that for L={a^n, n>=0}, there would be 2 states in DFA because there is no restriction on the value of n. However, what would be the no of states when n is restric...
Jayant Isswani
1.6k
views
Jayant Isswani
asked
Jan 27, 2018
Theory of Computation
finite-automata
minimal-state-automata
theory-of-computation
+
–
2
votes
0
answers
74
minimal dfa
Consider the following grammar: $S\rightarrow aA|bB$ $A\rightarrow aA|bB$ $B\rightarrow bB|ϵ$ Then the number of states in a minimal D.F.A of the above grammar is ______________ ?
Consider the following grammar:$S\rightarrow aA|bB$$A\rightarrow aA|bB$$B\rightarrow bB|ϵ$Then the number of states in a minimal D.F.A of the above grammar is __________...
junk_mayavi
419
views
junk_mayavi
asked
Jan 15, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
+
–
2
votes
1
answer
75
#states DFA
The minimum no of states required to construct a DFA accepting the language of binary strings which contain an equal no of (01) and (10) is
The minimum no of states required to construct a DFA accepting the language of binary strings which contain an equal no of (01) and (10) is
Tuhin Dutta
530
views
Tuhin Dutta
asked
Dec 31, 2017
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
1
votes
1
answer
76
MINIMAL DFA
Aakanchha
663
views
Aakanchha
asked
Dec 31, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
0
votes
0
answers
77
[Madeasy] the minimum number of states in DFA for given language
L = (0*1 + 1+ 0) I got minimal DFA with 5 state only, but in their answer, they have mentioned with minimum 6 states.
L = (0*1 + 1+ 0)I got minimal DFA with 5 state only, but in their answer, they have mentioned with minimum 6 states.
techbrk3
605
views
techbrk3
asked
Dec 20, 2017
Theory of Computation
minimal-state-automata
+
–
0
votes
0
answers
78
No of states in Min DFA
No of states in Min DFA, that accepts (1)* over {0,1} alphabets is 1 states 2 states None of these
No of states in Min DFA, that accepts (1)* over {0,1} alphabets is1 states2 statesNone of these
hacker16
293
views
hacker16
asked
Dec 17, 2017
Theory of Computation
minimal-state-automata
theory-of-computation
+
–
0
votes
1
answer
79
minimal Dfa
Parshu gate
632
views
Parshu gate
asked
Dec 3, 2017
Theory of Computation
number-of-states
minimal-state-automata
theory-of-computation
+
–
2
votes
2
answers
80
DFA no of states
What is the min no. of states required in DFA which accepts all strings starting with 1 and whose decimal value is divisible by 7?
What is the min no. of states required in DFA which accepts all strings starting with 1 and whose decimal value is divisible by 7?
Tuhin Dutta
1.1k
views
Tuhin Dutta
asked
Nov 30, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
1
votes
1
answer
81
Minimum DFA Construction
Construct the minimum DFA accepting language L over {a, b} where the 5th symbol and the 10th symbol from LHS is different. It is given that the minimum DFA has 12 states. But I am getting many more states. Could someone please provide a diagram that involves only 12 states?
Construct the minimum DFA accepting language L over {a, b} where the 5th symbol and the 10th symbol from LHS is different. It is given that the minimum DFA has 12 states....
humblefool
990
views
humblefool
asked
Nov 16, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
2
votes
1
answer
82
TOC :- Number of states in DFA
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
rahul sharma 5
953
views
rahul sharma 5
asked
Nov 9, 2017
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
number-of-states
+
–
2
votes
2
answers
83
Number of states in a minimal DFA construction
Suppose L is a regular language of all a's and b's where the number of a's is divisible by m and the number of b's is divisible by n. If M is the minimal DFA accepting language L, then what is the number of states in M ? Is it nm or (n+1)(m+1) ?
Suppose L is a regular language of all a's and b's where the number of a's is divisible by m and the number of b's is divisible by n. If M is the minimal DFA accepting la...
humblefool
1.7k
views
humblefool
asked
Nov 2, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
0
answers
84
Minimized DFA
What is the number of states in a minimal DFA accepting the language which contains all strings that either begin or end (or both) with 01 ? Assume alphabet set as {0,1} I got the answer but it was time consuming. Any hack on drawing its intuitive NFA ? as then conversion would be easier from NFA to DFA.
What is the number of states in a minimal DFA accepting the language which contains all strings that either begin or end (or both) with 01 ? Assume alphabet set as {0,1}...
just_bhavana
495
views
just_bhavana
asked
Oct 31, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
0
votes
1
answer
85
MadeEasy WorkBook: Theory of Computation - Minimum State Automata
IF a number is divisible by say any integer X then what will be the minimum states required in DFA?
IF a number is divisible by say any integer X then what will be the minimum states required in DFA?
Pranav Madhani
445
views
Pranav Madhani
asked
Oct 26, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
made-easy-booklet
+
–
5
votes
2
answers
86
How to make a minimal DFA
Draw a minimal DFA which accepts a language L over {a,b} 01 [ ((10) * + 111) * + 0 ] * 1
Draw a minimal DFA which accepts a language L over {a,b}01 [ ((10) * + 111) * + 0 ] * 1
dragonball
725
views
dragonball
asked
Oct 26, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
+
–
1
votes
0
answers
87
DFA minimization
Given : DFA. Minimum number of states required to construct an equivalent NFA is a)2 b)3 c)4 d)6 PS: how can we minimize if initial and final states of DFAare not given ?
Given : DFA.Minimum number of states required to construct an equivalent NFA isa)2b)3c)4d)6PS: how can we minimize if initial and final states of DFAare not given ?
shaurya vardhan
917
views
shaurya vardhan
asked
Oct 24, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
5
votes
3
answers
88
TOC: Number of states in minimum DFA
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA {q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA{q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
Manu Thakur
2.2k
views
Manu Thakur
asked
Oct 9, 2017
Theory of Computation
minimal-state-automata
theory-of-computation
finite-automata
+
–
1
votes
1
answer
89
Theory-of-computation DFA
Design a minimal DFA accepting L={w ; atleast one 'a' in w is not immediately followed by 'b'}
Design a minimal DFA accepting L={w ; atleast one 'a' in w is not immediately followed by 'b'}
MayankSharma
520
views
MayankSharma
asked
Oct 3, 2017
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
0
votes
4
answers
90
minimal DFA
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
construct the minimal DFA for the language L={ 3rd symbol from the R.H.S is 'a'} and ∈={a.b}.
jaiganeshcse94
886
views
jaiganeshcse94
asked
Sep 26, 2017
Theory of Computation
finite-automata
theory-of-computation
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