440 views
3 votes
3 votes

The number of possible finite automaton with 2 states a0 and a1 where a0 is always initial state over the alphabet {p, q, r} which accept empty language is _______
 

1 Answer

2 votes
2 votes

Empty language = { }  or $\phi$

condition : 1  No final States

  p q q
a0(Initial state) a0/a1 a0/a1 a0/a1
a1 a0/a1 a0/a1 a0/a1

In that case , we doesn't have any final state...so every input we have 2 choices either we go to state a0 or a1

therefore ,  2 x 2 x 2 x 2 x 2 x 2 = 26 ways

since no final states therefore it accepting the empty language

Condition : 2  a1 is a final state

  p q q
a0(Initial state) a0 a0 a0
a1 (final state) a0/a1 a0/a1 a0/a1

 here , if a1 is final state then if we are in state a0 ...and In any input we doesn't change our state from a0 to a1 ..cuz a1 is final state , therefore it's accept the string but here we only accept the empty language right ??

therefore , when we are in a0 state we have only  1 choice .. in any input p , q ,r we stay in the same state which is a0

but when we are at state a1 state we have 2 choices either we stay in a1 or go to a0 state

therefore ,   2 x 2 x 2  = 23 ways

Total number of ways =  26 + 23 = 72 ways

Related questions

2 votes
2 votes
2 answers
1
Balaji Jegan asked Oct 1, 2018
1,442 views
The number of possible finite automaton with 3 states a0, a1 and a2 where a0 is always initial state over the alphabet {p, q} which accept empty language is _______
0 votes
0 votes
1 answer
2
Harshitha 123 asked Aug 9, 2018
287 views
Number of FA's possible for two states X,Y over the input alphabet {a,b} where X is always the initial state and the FA should accept only empty language ?