Search code examples
regexfsmcomputation

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

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?

Solution

  • 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.