312 views
0 votes
0 votes
Consider the Minimal Finite Automata that accept all the strings of a’s & b’s where no. of a’s is congruent to 2 mod 3. The no. of states in this automata is

2 Answers

0 votes
0 votes
This automaton will have 3 as the minimum number of states.

Your problem statement is $n_a(w) \equiv2mod3$ which is same as saying $n_a(w)mod3=2$

There will be three equivalence classes in which this DFA would divide your input into.

Class 0: All such strings with $n_a(w)mod3=0$

Class 1: $n_a(w)mod3=1$

Clas 2: $n_a(w)mod3=2$
0 votes
0 votes
minimum no of states=3

MOD 3=

No of states=3/2=1.5=2states

total no of states=2+1(extra state)=3

Related questions

0 votes
0 votes
0 answers
1
prashant dubey asked Apr 27, 2019
255 views
The minimum no. of states required to construct DFA which can accept length of the string is devisable by 4 where input string is 0,1Please also construct dfa
0 votes
0 votes
2 answers
2
altamash asked Dec 25, 2018
242 views
{w1 x w2|w1,x,w2∈(a+b)*,w1=w2}it is regular ?????
0 votes
0 votes
0 answers
3
altamash asked Dec 25, 2018
186 views
explain why it is CFL?
0 votes
0 votes
1 answer
4
altamash asked Sep 21, 2018
270 views
what is minimum number of states of NFA which accepts language{abab^n|n>=0} U{aba^n|n>=0}