Register
Filter

Questions by Soumya29

0 votes
0 answers
2
Testbook Test Series: Theory of Computation - Minimal State Automata
$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______. Approach ?
$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______.Approach ?
0 votes
0 answers
7
Binary Tree
I know the answer. But is there any general FORMULA for it? If yes, please provide the complete derivation of it. In the solution, they used $\rightarrow 2^{h-1}+1.$ I tried but I am not able to derive it.
I know the answer. But is there any general FORMULA for it?If yes, please provide the complete derivation of it. In the solution, they used $\rightarrow 2^{h-1}+1.$ I tri...
1 votes
2 answers
9
Peter Linz 4th edition Ex-1.2 -Q10
Q- Prove or Disprove the following claim- $(L^R)^*=(L^*)^R$ for all languages.
Q- Prove or Disprove the following claim- $(L^R)^*=(L^*)^R$for all languages.
0 votes
3 answers
10
Self Doubt
How to evaluate this quickly? $\large\sum^{20}_{r=0}(-1)^r\binom{r+2}{r}\\OR\\\large\sum^{20}_{r=0}(-1)^r(r+2)(r+1)$
How to evaluate this quickly?$\large\sum^{20}_{r=0}(-1)^r\binom{r+2}{r}\\OR\\\large\sum^{20}_{r=0}(-1)^r(r+2)(r+1)$
4 votes
1 answer
14
Self Doubt. Related to https://gateoverflow.in/94634/gate1988-13ii#c216658.
1. If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e $f:S \rightarrow S$ is a surjective function), then $f$ is one-to-one.
1. If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e $f:S \rightarrow S$ is a surjective function), then $f$ is one-to-one.
1 votes
1 answer
15
Self Doubt
The smallest number of states a TM can have?
The smallest number of states a TM can have?
0 votes
1 answer
16
Decidability
L= {<G> | G is CFG and G is NOT ambiguous} . L is TM recognizable or not even TM recognizable?
L= {<G | G is CFG and G is NOT ambiguous} .L is TM recognizable or not even TM recognizable?
2 votes
3 answers
17
Kenneth Rosen Edition 7 Exercise 10.8 Question 23 (Page No. 734)
Find the edge chromatic numbers of a) Cn, where n ≥ 3. (Cycle with n vertices) b) Wn, where n ≥ 3 (Wheel with n vertices) c)Complete graph with n vertices.
Find the edge chromatic numbers ofa) Cn, where n ≥ 3. (Cycle with n vertices)b) Wn, where n ≥ 3 (Wheel with n vertices)c)Complete graph with n vertices.