I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of.

I have a question to find out the relationship between two languages $L_1$ and $L_2$:


$S \to aSa|bS|e$

$L_2 \to L((ab+ba)^*)$

My question is, does it mean that $L(ab+ba)$ is the set $\{ab, ba\}$?

I mean, $L(ab+ba) = L(ab)\cup L(ba)$


This link confirms my intuition that $L(R)$ where $R$ is a regular expressions simply means "the language produced by the regular expression $R$".

In that case, $ab \in L_2$ but $ab \notin L_1$

In case link is down:

Operators used in regular expressions include:

Union: If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression. L(R1|R2) = L(R1) U L(R2).

Concatenation: If R1 and R2 are regular expressions, then R1R2 (also written as R1.R2) is also a regular expression. L(R1R2) = L(R1) concatenated with L(R2).

Kleene closure: If R1 is a regular expression, then R1* (the Kleene closure of R1) is also a regular expression. L(R1*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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