Can i count the number of digits in a string with FSM?

Question

I want to count the number of digits in a string which can include non digits(aa11aa1a). Can i solve this problem with a Finite State Machine? Can this problem be represented as regular expression?

What if i want to know whether the count is "X" or not, does it change the nature problem? To be more precise, is there 3 digits in this string? Is a FSM enough to solve the problem?

Answer 1

The second problem can be solved with a regular expression.

Consider: ^[^0-9]*[0-9][^0-9]*[0-9][^0-9]*[0-9][^0-9]*$.

You could also use groups: ^[^0-9]*([0-9][^0-9]*){3}$

I don't think you can use regular expressions alone to solve the first problem. But a solution using regular expressions (to remove all non-digits, or match a single digit) would be trivial.

Answer 2

If you just want to match 3 digits that's like

/[^0-9]*[0-9][^0-9]*[0-9][^0-9]*[0-9][^0-9]*/

If it matches the string contains exactly three digits.

Answer 3

Rather than using an explicit FSM, I'd suggest using a regular expression to take out all the non-digits and then just take the length of the resultant string. Alternatively, match your regex to individual digits and take the count of the number of matches (this would likely be less efficient, though). Or, the simplest way to do it (pseudocode):

count = 0

for char in string
    if char is a digit
        increment count

// For your second part
    if count > X
        count isn't X; done

if count < X
    count isn't X; done
else
    count is X; done