[!Note]

This article does NOT serve as a complete guide of the conversion between these three things. Instead, this article will only record some import or unusual rules during the conversion.

Regex To Automata

Basics

Usually, when discussing Regular Expression -> Automata, we are talking about Right Linear Regular Grammars. This will ensure all productions has the following format:

$$ \begin{aligned} A \to xB \ A \to y \end{aligned} $$

Converting Rules

In this case, we just convert non-terminal into automata node, and terminal as the char required for the corresponding state transaction.

Examples

Consider:

$$ \begin{aligned} A &\to xB \ B &\to yB | c \end{aligned} $$

Then the convert result will be:

stateDiagram-v2
    [*] --> A
    A --> B: x
    B --> B: y
    B --> [*]: c

Regex To Automata

It could be proved that (x|y)* and (x*|y)* are eventually equivalent.