Are the regular expressions (0*1*)* and (0 | 1)* the same?
Could someone provide a proof or intuitive disproof for that? I feel like it is true but I’m struggling to write a step by step proof.
Two different regular expressions or two grammars can generate the same languages as these do but the regular expressions or grammars are not the same. There is a standard method of constructing a non-deterministic finite state automaton from a regular expression and from that constructing a deterministic finite state automaton. That method will produce two different automata for the regular expressions in question. Though each one will recognize the same strings, they will go through different states in doing so.