Register

Recent questions tagged finite-automata

0 votes
1 answer
842
nfa theory of computation
The answer to this question is given as 6.
The answer to this question is given as 6.
User Avatar
0 votes
3 answers
843
CFL or not
It seemed like , this is textbook example of non-CFL language ; will require 2 comparisons . That means no complement exist was the answer , I was expecting. Why answer given is CFL , am I missing something ?
It seemed like , this is textbook example of non-CFL language ; will require 2 comparisons . That means no complement exist was the answer , I was expecting. Why answer g...
User Avatar
0 votes
0 answers
846
NFA design
NFA :
NFA :
User Avatar
1 votes
2 answers
847
DCFL or CFL ?
Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?
Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?
User Avatar
1 votes
1 answer
848
toc dfa
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
Construct minimal DFA which accepts set of all srings over {a,b} which starts and ends with the same symbol???
User Avatar
1 votes
2 answers
850
minimised Automata
Let $L=\{(a^p)^* \mid$ p is a prime number$\}$ and $\Sigma=\{a\}$ .The minimum number of states in NFA that accepts $L$ is?
Let $L=\{(a^p)^* \mid$ p is a prime number$\}$ and $\Sigma=\{a\}$ .The minimum number of states in NFA that accepts $L$ is?
User Avatar
1 votes
1 answer
851
DFA minimisation
Why no of states in a dfa(language having binary strings whose integer equivalent is divisible by n) where n = 8,12.., are different form a standard dfa where we say that no of states will be n-1(for n =2,3,5)?
Why no of states in a dfa(language having binary strings whose integer equivalent is divisible by n) where n = 8,12.., are different form a standard dfa where we say that...
User Avatar
0 votes
0 answers
852
FSM :
Please explain
Please explain
User Avatar
4 votes
1 answer
854
Minimum number of states
What is the No of states in Min.DFA on $ E={0,1,2} $which accepts the ternary no whose equivalent is divisible by $9?$
What is the No of states in Min.DFA on $ E={0,1,2} $which accepts the ternary no whose equivalent is divisible by $9?$
User Avatar
32 votes
3 answers
855
GATE CSE 1987 | Question: 2j
State whether the following statements are TRUE or FALSE: A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states.
State whether the following statements are TRUE or FALSE:A minimal DFA that is equivalent to an NDFA with $n$ nodes has always $2^{n}$ states.
User Avatar
0 votes
1 answer
856
Gate Practice Question
An NFA has 11 states of which 5 are final .If we convert this NFA into DFA atmost how many states can be final states ?
An NFA has 11 states of which 5 are final .If we convert this NFA into DFA atmost how many states can be final states ?
User Avatar
0 votes
0 answers
857
Theory-of-computation
I read the foll statement somewhere.. Is it true? In nfa if there is a dead configuration then its equivalent dfa may or may not have trap state. Acc to me it will always have a trap state for that particular nfa. ??
I read the foll statement somewhere..Is it true?In nfa if there is a dead configuration then its equivalent dfa may or may not have trap state.Acc to me it will always h...
User Avatar
0 votes
1 answer
860
Equivalency of diffetent automata
Write about the equivalency of different automata such as DFA, NFA, DPDA, NPDA, DTM, NTM. Which automata or machine can be converted to other machines and why? For example NFA can be converted to DFA, DPDA, NPDA, DTM, NTM.
Write about the equivalency of different automata such as DFA, NFA, DPDA, NPDA, DTM, NTM. Which automata or machine can be converted to other machines and why? For exampl...
User Avatar
0 votes
1 answer
864
#minimized-dfa
Minimized DFA for a*b* + b*a* and a+b+ + b+a+
Minimized DFA for a*b* + b*a*anda+b+ + b+a+
User Avatar
0 votes
1 answer
865
Theory of Computation (DFA & NFA)
1) if |L1| < |L2| then L1 must be finite Trye/False?
1) if |L1| < |L2| then L1 must be finite Trye/False?
User Avatar
7 votes
2 answers
867
Number of states in minimal finite automata
Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100. A. 102 B. 103 C. 104 D. 105
Number of states in minimal finite automata that accepts all binary strings that starts with 101 and is divisible by 100.A. 102B. 103C. 104D. 105
User Avatar
0 votes
1 answer
869
Finite Automata
Construct dfa for set of all strings where every pair of consecutive 0's occurs before any pair of adjacent 1's ?
Construct dfa for set of all strings where every pair of consecutive 0's occurs before any pair of adjacent 1's ?
User Avatar
5 votes
6 answers
870
Minimized DFA no of states || Peter Linz
$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$ Minimal DFA for the above language ?
$L = \left \{ a^nb \ ; n\geq 0 \right \} \cup \left \{ b^na \ ; n\geq 1 \right \}$Minimal DFA for the above language ?
User Avatar
Page: