New answers tagged

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
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
0 votes

Reference types

In Swift, there is a conscious distinction between "reference types" and "value types". classes and closures are reference types, structs, enums, and tuples are value types. If you ...
gnasher729'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
0 votes

Why is English not a regular language?

Interesting conversation. I think that the grammar of English is not regular, because the grammar was defined as programming language are defined. But natural spoken English (or any other language) is ...
Antonio Cano Gómez's user avatar
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

Top 50 recent answers are included