A frivolous problem with a deeper lesson

Many words can be spelled by stringing together chemical symbols. For example, sarcasm can be written S Ar Ca Sm using the symbols for sulfur, argon, calcium, and samarium. How would you write a program to determine whether a word can be written by stringing together chemical element abbreviations ignoring case? Obviously this isn’t a practical problem, but it illustrates a practical problem. You could solve the problem with a regular expression: (h|he|li|be|b|c|n|o|f|ne|na|mg|al|si| … |og)+ This solution could either be very efficient or very inefficient, depending on the inner workings of the software used to match the regular expression. A DFA (deterministic finite automata) regular expression engine would find a match, or report failure, linear time, i.e. the execution time would be proportional to the length of the string being matched. A NFA (nondeterministic finite automata) engine that uses backtracking could take exponential time. The root of the problem is the ambiguity in…