2 votes

Rational subsets of a monoid

Yes, it's a lifting of the monoid product $$x, y ∈ M ↦ xy ∈ M$$ onto a product $$A, B ∈ 𝔓M ↦ AB ∈ 𝔓M,$$ that makes the power-set $𝔓M$ of $M$ into a monoid, and $M$, itself, a sub-monoid of $𝔓M$ ...
NinjaDarth's user avatar
2 votes
Accepted

Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"

If you think about it, there are only 3 kinds of string not in your language: $$\varepsilon, 00...0 \text{ and } 11...1.$$ So when you read a string, left to right, there are only four states you need ...
Knogger's user avatar
  • 1,032
2 votes

Graph labyrinth solving sequence

Let $G_1, \dots, G_m$ be an enumeration of all strongly connected directed graphs on at most $n$ vertices in which every vertex has out-degree 2 (the corresponding edges labelled $a,b$). The algorithm ...
Yuval Filmus's user avatar
1 vote

Regular expression vs rational expression

The usage that I've seen, have been told of, and that I recommend is "rational" if the underlying monoid is non-free, "regular" for free monoids. Examples showing this, which I've ...
NinjaDarth's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible