retagged by
920 views
5 votes
5 votes
The number of possible Deterministic Finite Automation with two states $q_0$ and $q_1$, where $q_0$ is always the initial state over the alphabet $\left \{ a,b \right \}$ which accept empty language is : ____________.
retagged by

1 Answer

Best answer
8 votes
8 votes

Given,


Machine = DFA.

Input alphabats = { a,b}

No. of states = 2 { q0, q1}.

Initial state = q0.

Language accepted = phi.


case-1. When both q0 and q1 are non-final. 

Total possible transition at q0 = 2 * 2  { 2 for a and 2 for b}

Total possible transition at q1 = 2 * 2  { 2 for a and 2 for b}

Total possible config. for eqv. DFA = 4 * 4 = 16


case- 2. When q0 - non-final and q1- final.

Total possible transition at q0 = 1 { a and b can not make a trasition to final state q1 other wise accepted language whould not be phi.}

Total possible transition at q1 = 2 * 2  { 2 for a and 2 for b}

Total possible config. for eqv. DFA = 1* 4 = 4.



total No. of possible DFA’s = 16+4 = 20

selected by
Answer:

Related questions

1 votes
1 votes
5 answers
1
Bikram asked Jan 24, 2017
714 views
$S\rightarrow A0 B$$A\rightarrow BB \mid 0$$B\rightarrow AA \mid 1$ The number of terminal strings of length $5$ generated by the context-free grammar shown above is ____...
4 votes
4 votes
2 answers
2
Bikram asked Jan 24, 2017
469 views
The value of the expression $1 - 6 + 2 - 7 + 3 - 8 +$……… to $100$ terms is __________.
5 votes
5 votes
2 answers
4
Bikram asked Jan 24, 2017
803 views
$HCF$ of two numbers is $23$ and other two factors of their $LCM$ are $13 $&$ 14$. The largest of two numbers is _________