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)?


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.


closed as unclear what you're asking by David Richerby, Evil, Rick Decker, Juho, fade2black Oct 11 '17 at 10:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ 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. $\endgroup$ – D.W. Sep 22 '17 at 4:20
  • 1
    $\begingroup$ TCS is rather simple this way: look at the definition. $\endgroup$ – Raphael Sep 22 '17 at 5:44
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Sep 22 '17 at 5:44
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Sep 22 '17 at 11:15

The symbols you quote have the following meaning:

  • $+$ 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)$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.