# How to read regular expressions? [closed]

Consider the following regular expressions

letter = a + b + c + d

LETTER = A + B + C + D
digit = 4+5+6+7+9
R1 = (LETTER + digit + !) • (letter • digit)∗• (letter + digit)
R2 = (LETTER + digit + ?) • (letter + digit)∗• (LETTER + digit)
R3 = (digit + ? + !) • (letter∗• digit∗)∗• (LETTER + letter)
R4 = (digit • letter + ? + !) • (letter∗• digit∗) • (LETTER)


I'm not sure what some of the characters mean ('+' , '•' , '*')?

Do I read regex backwards when check if a string is an element of L(R1)?

FOR EXAMPLE: !5aA ELEMENT/NOT ELEMENT L(R1)

R1 = (LETTER + digit + !) • (letter • digit)∗• (letter + digit)

!5aA is an element of L(R1) I would think, but that's just a guess.


If someone can point me in the right direction to read a regex like this it would be greatly appreciated.

EDIT: So after considering Yuval answer this starts to make a whole lot of sense to me so thank you. It seems like the correct language for the string !5aA is L(R3) AND/OR L(R4) not sure which exactly yet, maybe its both. I like to think the + as OR's (not multiples) the • as a concatenation (or no concatenations) and * as all combinations. Treating • as multiplication using the commutative property holds true, makes sense for the order of the chars.

• Please ask only one question per question. You might want to take a look at en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form. – D.W. Sep 22 '17 at 4:20
• TCS is rather simple this way: look at the definition. – Raphael Sep 22 '17 at 5:44
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Sep 22 '17 at 5:44
• There must be hundreds of resources online and in textbooks that tell you how to read a regular expression. Did you read any of them? What didn't you understand in them? It doesn't seem to be worth anyone's time to replicate a huge number of existing resources without even knowing what's wrong with them. – David Richerby Sep 22 '17 at 11:15

• $+$ means or: $L(r_1 + r_2) = L(r_1) \cup L(r_2)$.
• $\cdot$ means concatenation: $L(r_1 \cdot r_2) = \{ xy : x \in L(r_1), y \in L(r_2) \}$.
• $^*$ means iteration: $L(r^*) = \{ \epsilon \} \cup L(r) \cup L(r \cdot r) \cup L(r \cdot r \cdot r) \cup \cdots$.
(Here $\epsilon$ is the empty word, sometimes denoted $\lambda$.)
Now let us consider your example: $$R_1 = (\mathsf{LETTER} + \mathsf{digit} + \mathsf{!}) \cdot (\mathsf{letter} \cdot \mathsf{digit})^* \cdot (\mathsf{letter} + \mathsf{digit}).$$ All words in $L(R_1)$ end in a lowercase letter $a,b,c,d$ or in a digit $4,5,6,7,9$. The word $!5aA$ ends in neither, so doesn't belong to $L(R_1)$.