What do the regular expression operations + and . mean in the context of finite state automata?

Question

Suppose you have the alphabet $\Sigma = \{0, 1, 2, 5\}$ where the symbols represent the value of coins, and you're given the regular expression $e = (1.1) + 2$ which is supposed to describe all the possible ways you can pay for something costing $2$.

Given this, how can I deduce what . and + do? Are there agreed upon definitions for these symbols which are taken as standard?

Answer 1

You can't deduce it, these (standard) terms have a definition. These expressions describe sets of words.

• when a character appears, eg 1, think of it as the singleton containing that character, eg $\{1\}$.
• The point (I'll use mathjax \cdot as in $1\cdot 1 = 11$) seems to be the concatenation : if $A$ and $B$ are sets of words in your alphabet, then $ A \cdot B := \{ab \big| \ a\in A \textrm{ and } b \in B \}$. Often, concatenation is made implicit and one writes $AB$ instead of $A \cdot B$.
• The + is union. $A+B$ means $A \cup B$.

eg let's study the expression $e$ :

The set $1\cdot 1$ contains only one element : the word $11$.

Hence, $e = \{11\} + \{2\} = \{11;2\}$.