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.

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

| cite | improve this answer | |

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