<p>It is of course subjective, but I think there are at least two factors that can influence whether expression or DFA is simpler:</p>
<ol>
<li><p>What habits and practice do you have with each formalism.</p>
</li>
<li><p>The shape of the particular language you want to express.</p>
</li>
</ol>
<p>The point 1 is self-explanatory, you get used to some formalism and you progressively get better at expressing things with it as you practice. For your example language, you can be inspired by &quot;even numbers of <span class="math-container">$a$</span>'s&quot; which is <span class="math-container">$(b^*ab^*a)^*b^*$</span>, and replace <span class="math-container">$a$</span> by <span class="math-container">$000$</span> and <span class="math-container">$b$</span> by &quot;not containing <span class="math-container">$000$</span>&quot; which is <span class="math-container">$(1+01+001)^*$</span>. You also need to add at the end <span class="math-container">$(\varepsilon+0+00)$</span> to allow for final zeroes, and there you have it. I'm assuming here you meant disjoint occurences of <span class="math-container">$000$</span>, otherwise you can replace <span class="math-container">$a$</span> by <span class="math-container">$000(00)^*1$</span> and <span class="math-container">$b$</span> by <span class="math-container">$(01+(00)^*1)^*$</span> so that you only care about odd intervals of <span class="math-container">$0$</span>. Again you need additional options for the end of the word, but the main idea is here. Maybe for some people more algebra oriented and less machine oriented, this process can be quicker than coming up with a DFA.</p>
<p>But most importantly and objectively, there is a feature that is an essential part of regular expressions but not DFAs: nondeterminism. Take the classic language &quot;there is an <span class="math-container">$a$</span> <span class="math-container">$5$</span> letters before the end&quot;, it is easy with an expression: <span class="math-container">$(a+b)^*a(a+b)^4$</span>, but the minimal DFA has <span class="math-container">$2^5=32$</span> states, so for sure it's harder in this case. Coming up with an NFA is a lot easier, but it can also require some practice to be at ease with nondeterminism in automata.
So if your language is easily defined thanks to nondeterminism, an expression will likely be more convenient than a DFA. If on the other hand your intuition of the language relies on complementation, it will likely be easier to do with a DFA, since they have this feature while expressions do not.</p>

CC BY-SA 4.0
2023-01-04T16:40:47.303Z
2023-01-05T09:29:03.180Z
2023-01-05T09:29:03.180Z
Denis
<p>When I am asked to construct a regular expression and <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton" rel="nofollow noreferrer">DFA</a> that would accept a language <span class="math-container">$L$</span>, I usually find it <strong>much easier</strong> to construct the DFA (almost coming mechanically for me) than it is to construct a regular expression of the same language. I often take <em>much</em> longer to construct a regular expression for the same DFA that I constructed almost immediately. Most of my friends also share a similar frustration.</p>
<p>One can &quot;of course&quot; use the DFA, and say the Elimination algorithm, to construct the regular expression from the DFA directly to avoid this problem, since they are computationally equivalent.</p>
<p>However, my question is more &quot;philosophical&quot;. Is there a reason why we find it inherently a lot simpler to construct DFAs vs an equivalent regular expression?</p>
<p>A concrete example is the language <span class="math-container">$$L=\{w\in \{0,1\}^\ast | ~000 \text{ appears an even number of times in } w\}.$$</span> I could come up with the DFA within a few minutes, but an equivalent regular expression took me longer than an hour.</p>

<cc.complexity-theory><automata-theory>
Are regular expressions inherently more difficult to construct than DFAs for humans?
user3508551
# Are regular expressions inherently more difficult to construct than DFAs for humans?

(Asked by: username_0 on 2023-01-04)

When I am asked to construct a regular expression and [DFA](https://en.wikipedia.org/wiki/Deterministic_finite_automaton) that would accept a language $L$, I usually find it **much easier** to construct the DFA (almost coming mechanically for me) than it is to construct a regular expression of the same language. I often take *much* longer to construct a regular expression for the same DFA that I constructed almost immediately. Most of my friends also share a similar frustration.

One can "of course" use the DFA, and say the Elimination algorithm, to construct the regular expression from the DFA directly to avoid this problem, since they are computationally equivalent.

However, my question is more "philosophical". Is there a reason why we find it inherently a lot simpler to construct DFAs vs an equivalent regular expression?

A concrete example is the language $$L=\{w\in \{0,1\}^\ast | ~000 \text{ appears an even number of times in } w\}.$$ I could come up with the DFA within a few minutes, but an equivalent regular expression took me longer than an hour.

**Tags:** cc.complexity-theory, automata-theory

---

## 1 answers

### Answer by username_1 on 2023-01-04. Score: 8

It is of course subjective, but I think there are at least two factors that can influence whether expression or DFA is simpler:

1. What habits and practice do you have with each formalism.
2. The shape of the particular language you want to express.

The point 1 is self-explanatory, you get used to some formalism and you progressively get better at expressing things with it as you practice. For your example language, you can be inspired by "even numbers of $a$'s" which is $(b^\*ab^\*a)^\*b^\*$, and replace $a$ by $000$ and $b$ by "not containing $000$" which is $(1+01+001)^\*$. You also need to add at the end $(\varepsilon+0+00)$ to allow for final zeroes, and there you have it. I'm assuming here you meant disjoint occurences of $000$, otherwise you can replace $a$ by $000(00)^\*1$ and $b$ by $(01+(00)^\*1)^\*$ so that you only care about odd intervals of $0$. Again you need additional options for the end of the word, but the main idea is here. Maybe for some people more algebra oriented and less machine oriented, this process can be quicker than coming up with a DFA.

But most importantly and objectively, there is a feature that is an essential part of regular expressions but not DFAs: nondeterminism. Take the classic language "there is an $a$ $5$ letters before the end", it is easy with an expression: $(a+b)^\*a(a+b)^4$, but the minimal DFA has $2^5=32$ states, so for sure it's harder in this case. Coming up with an NFA is a lot easier, but it can also require some practice to be at ease with nondeterminism in automata.
So if your language is easily defined thanks to nondeterminism, an expression will likely be more convenient than a DFA. If on the other hand your intuition of the language relies on complementation, it will likely be easier to do with a DFA, since they have this feature while expressions do not.


---

