non-deterministic automaton and regular expression

Question

I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet $\{a,b,c\}$ that accept all and only those strings that contain exactly three a's, three b's, or three c's, not necessarily consecutively .for example; strings l.ike $\{aaa, abaab, abbcccccccccccbaaa,cbccbbbbbbb,..\}$ is accepted.

Thanks all

Answer 1

In regular expressions it would be:

[bc]*a[bc]*a[bc]*a[bc]*

(logical or with its versions with b and c, left as exercise for the reader)

https://regex101.com/r/mI5dM4/1

(Only the 3 a version, and include \b for word boundary)

It matches any (possibly empty) sequence of non-'a' characters, exactly 3 times interrupted by an 'a'.

Answer 2

the simplest way is that define NFA with states like $q_{ijk}$ where $i,j,k \in \{0,1,2,3,n \}$ that $i$ determine the number of $a$ and $j$ determine the number of $b$ and $k$ determine the number of $c$. when an index is $n$ means its greater than $3$. you can easly define function of NFA as when read $a$ just from $q_{ijk}$ goto $q_{i+1jk}$ and if $i=n$ stay at the state. start state is $q_{000}$ and all $q_{ijk}$ that at leas one of its index is 3 is the final state. its almost DFA so you can decrease the number of state if you want.