Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Some useful problems
Recent questions tagged finite-automata
1
votes
1
answer
541
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
542
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.
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 co...
Subham Nagar
423
views
Subham Nagar
asked
May 6, 2018
Theory of Computation
test-series
finite-automata
theory-of-computation
+
–
0
votes
1
answer
543
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.0k
views
kislaya Pant
asked
May 5, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
+
–
1
votes
0
answers
544
Peter Linz Edition 4 Exercise 2.1 Question 8.c (Page No. 47)
how to draw dfa for this? L= {w: there are at most two runs of a’s of length three}.
how to draw dfa for this?L= {w: there are at most two runs of a’s of length three}.
Ananya Jaiswal 1
2.1k
views
Ananya Jaiswal 1
asked
May 3, 2018
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+
–
4
votes
2
answers
545
ISRO2018-26
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
The $FSM$ (Finite State Machine) machine pictured in the figure aboveComplements a given bit patternFinds $2's$ complement of a given bit patternIncrements a given bit pa...
Arjun
7.0k
views
Arjun
asked
Apr 22, 2018
Theory of Computation
isro2018
finite-automata
theory-of-computation
+
–
0
votes
1
answer
546
Peter Linz Edition 4 (Page No. 52)
Help me understand this statement from Theory of Computation by Peter Linz "If between two vertices vi and vj there is any walk labeled w, then there must be some walk labeled w of length no more than Λ + (1 + Λ) |w|, ... I am also having difficulty in understand extended transition function for an nfa , would be really helpful if someone could explain that.
Help me understand this statement from Theory of Computation by Peter Linz"If between two vertices vi and vj there is any walk labeled w, then there must be some walk la...
ankit aingh
1.3k
views
ankit aingh
asked
Apr 18, 2018
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
+
–
0
votes
1
answer
547
Regular expression
Prince Sindhiya
310
views
Prince Sindhiya
asked
Apr 10, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
1
answer
548
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.6k
views
smsubham
asked
Apr 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
0
answers
549
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?
Can you give an example of NFA which has n states and its corresponding DFA has 2^n states?
smsubham
800
views
smsubham
asked
Apr 8, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
1
votes
1
answer
550
Peter Linz Edition 4 Exercise 2.2 Question 10 (Page No. 55)
Also is this nfa possible with less than three states??
Also is this nfa possible with less than three states??
meghna
526
views
meghna
asked
Apr 7, 2018
Theory of Computation
peter-linz
peter-linz-edition4
finite-automata
theory-of-computation
+
–
1
votes
3
answers
551
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 ... grammar 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?
$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 ...
Sourav_35
1.6k
views
Sourav_35
asked
Apr 6, 2018
Theory of Computation
regular-grammar
theory-of-computation
finite-automata
+
–
3
votes
1
answer
552
Time complexity to minimize Finite Automata
According to this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo) then why it is said that Minimizing Finite Automata is computationally hard according to this link ?
According to this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo) then why it is said that Minimizing Fin...
ankitgupta.1729
1.5k
views
ankitgupta.1729
asked
Mar 27, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
0
votes
1
answer
553
Complementation of DFA
Complementation of DFA works for all DFA is it true ? Given DFA, a should be followed by a 'b', In the complementation of this DFA the string aab is getting accepted a is getting followed by a 'b'
Complementation of DFA works for all DFA is it true ?Given DFA, a should be followed by a 'b',In the complementation of this DFA the string aab is getting accepted a is g...
sanju77767
888
views
sanju77767
asked
Mar 18, 2018
Theory of Computation
finite-automata
theory-of-computation
+
–
0
votes
2
answers
554
finite automata
Draw the DFA for (a*b +b*a)
Draw the DFA for (a*b +b*a)
varunraj
560
views
varunraj
asked
Mar 17, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
0
votes
1
answer
555
Self doubt
Is dead state necessary in minimal DFA?
Is dead state necessary in minimal DFA?
Mk Utkarsh
726
views
Mk Utkarsh
asked
Mar 16, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
0
votes
1
answer
556
THEORY OF COMPUTER SCIENCE BY KLP MISHRA
Construct a DFA such that it accepts all strings over $\{a,b\}$ in which there are at least two occurrences of $b$ between any two occurrences of $a$.
Construct a DFA such that it accepts all strings over $\{a,b\}$ in which there are at least two occurrences of $b$ between any two occurrences of $a$.
Sourav_35
2.1k
views
Sourav_35
asked
Mar 15, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
3
votes
1
answer
557
#TOC Doubt - Regular expressions
Part A: Given : (b|ab*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?
Part A:Given : (b|ab*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 f...
ashishgateashish
1.1k
views
ashishgateashish
asked
Mar 13, 2018
Theory of Computation
regular-expression
finite-automata
theory-of-computation
+
–
1
votes
0
answers
558
Dfa to regex
please verify the regex
please verify the regex
Mk Utkarsh
401
views
Mk Utkarsh
asked
Mar 12, 2018
Theory of Computation
theory-of-computation
finite-automata
regular-expression
+
–
1
votes
1
answer
559
Automata
If $L1$ is regular language and $L2$ is unknown language then what can we say about $L1-L2$. 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 ... 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?
If $L1$ is regular language and $L2$ is unknown language then what can we say about $L1-L2$. Will it be regular or not?I think it will be regular because even if $L2$ is ...
hrcule
318
views
hrcule
asked
Mar 10, 2018
Theory of Computation
theory-of-computation
regular-language
finite-automata
+
–
3
votes
1
answer
560
Finite Automata
What's is the meaning of the statement:- An automatic is a cognitive device and a grammar is a generative device. What does the word cognitive and generative mean in this respect.
What's is the meaning of the statement:- An automatic is a cognitive device and a grammar is a generative device. What does the word cognitive and generative mean in this...
hrcule
1.2k
views
hrcule
asked
Mar 10, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
1
answer
561
test_series
Consider the DFA M : Number of distinct strings of length $3$ such that $\delta(q_{0},w) = q_{0}$ $10$ $14$ $18$ $20$
Consider the DFA M :Number of distinct strings of length $3$ such that $\delta(q_{0},w) = q_{0}$$10$$14$$18$$20$
shivanisrivarshini
420
views
shivanisrivarshini
asked
Mar 7, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
1
answer
562
Introduction to Computer Theory
Give Regular Expression for Language of all those strings which do not contain the substring ‘bb’. Also draw its DFA.
Give Regular Expression for Language of all those strings which do not contain the substring ‘bb’. Also draw its DFA.
The Capricorn
312
views
The Capricorn
asked
Mar 5, 2018
Theory of Computation
finite-automata
theory-of-computation
+
–
1
votes
1
answer
563
Introduction to Computer Theory
Give Regular Expression for the Language of all those strings which end with ‘aa’ or ‘ab’ and have odd length. Also, draw its DFA.
Give Regular Expression for the Language of all those strings which end with ‘aa’ or ‘ab’ and have odd length. Also, draw its DFA.
The Capricorn
256
views
The Capricorn
asked
Mar 5, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
1
answer
564
Introduction to computer theory
Draw a Finite Automata for the language of all strings which end with 'ab' and have even length.
Draw a Finite Automata for the language of all strings which end with 'ab' and have even length.
The Capricorn
262
views
The Capricorn
asked
Mar 4, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
0
answers
565
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 \}$
$\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 | \...
Mk Utkarsh
465
views
Mk Utkarsh
asked
Mar 4, 2018
Theory of Computation
theory-of-computation
finite-automata
+
–
1
votes
0
answers
566
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 $\}$ ???
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 $\}$ ???
Dharmesh Gusai
358
views
Dharmesh Gusai
asked
Mar 4, 2018
Theory of Computation
regular-expression
theory-of-computation
finite-automata
regular-language
+
–
1
votes
1
answer
567
Language accepted by given NFA
Language accepted by following NFA and number of states in DFA accepting that Language are: $\{a^n|n=2k,kϵN\}$ and 2 $\{a^{2n}|n=2k,kϵN\}$ and 2 $\{a^n|n=2k,kϵ N\}$ and 3 $\{a^{2n}|n=2k,kϵ N\}$ and 3
Language accepted by following NFA and number of states in DFA accepting that Language are:$\{a^n|n=2k,kϵN\}$ and 2$\{a^{2n}|n=2k,kϵN\}$ and 2$\{a^n|n=2k,kϵ N\}$ and 3...
GateAspirant999
1.0k
views
GateAspirant999
asked
Mar 2, 2018
Theory of Computation
finite-automata
non-determinism
theory-of-computation
+
–
2
votes
1
answer
568
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?
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 ...
Mamta Satywali
1.3k
views
Mamta Satywali
asked
Mar 2, 2018
Theory of Computation
theory-of-computation
regular-language
finite-automata
+
–
1
votes
2
answers
569
NFA-E to DFA conversion. (which is the correct solution?)
1. Which solution is correct? (or both wrong!) 2. Does every 'DFA equivalent' of any NFA has same starting state? if not, please give any smallest example.
1. Which solution is correct? (or both wrong!)2. Does every 'DFA equivalent' of any NFA has same starting state? if not, please give any smallest example.
ashishgateashish
2.4k
views
ashishgateashish
asked
Feb 27, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
1
votes
0
answers
570
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
569
views
ankitgupta.1729
asked
Feb 25, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
+
–
Page:
« prev
1
...
14
15
16
17
18
19
20
21
22
23
24
...
35
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register