1,034 views
1 votes
1 votes

Language accepted by following NFA and number of states in DFA accepting that Language are:

  1. $\{a^n|n=2k,kϵN\}$ and 2

  2. $\{a^{2n}|n=2k,kϵN\}$ and 2

  3. $\{a^n|n=2k,kϵ N\}$ and 3

  4. $\{a^{2n}|n=2k,kϵ N\}$ and 3 

1 Answer

Best answer
1 votes
1 votes

(1) since from the initial state in the given NFA, if one encounters even number of  a's , then and only then reaches final states. For example, from state S , for string "aaaa", one reaches the bottom right-most state. But, as one can notice, it also has an epsilon-transition to S, which is a final state. Hence, we can conclude here that this NFA accepts strings having even number of a's. 

Design of DFA is pretty trivial and hence, left as an exercise for the person who asked this question.

Thank You.

selected by

Related questions

0 votes
0 votes
0 answers
2
sripo asked Oct 16, 2018
393 views
For the language which ends with 01 or 11 or 10 or 11 for $\sum$={0,1}* .Is dfa possible for this language?
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
Mahesha999 asked Dec 25, 2016
1,821 views
Consider the NFA below:The above NFA acceptes all those binary strings which represents the decimal numbers and area. divisible by 6 onlyb. dividible by 2 and 3 onlyc. di...