0
$\begingroup$

I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses.

Suppose we have two regular languages, $L_1$ and $L_2$, with a common alphabet.

The union of $L_1, L_2$ is $\{x:x∈L_1∨x∈L_2\}$

Does this mean that, for any string $s \in L_1$, we also have $s \in L_2$?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
9
$\begingroup$

I see two possible points of confusion in your question, and I will address them separately.

  1. What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union."

  2. "The union of $L_1,L_2$ is $\{x:x∈L_1∨x∈L_2\}$ Does this mean that, for any string $s∈L_1$, we also have $s∈L_2$?"

What is "Closure Under Union"?

Regular languages are a class of languages that exhibit the closure property with the union operation.

The closure property means that when an operation is applied to language(s) of a certain class the resulting language will also be of that class.

In this case the class of languages is the regular languages and the operation is union.

So all this means is that the union of two regular languages is also a regular language.

What is the union of two languages?

Languages can be thought of as sets of strings, so the union operation works the same way as in typical Set Theory.

I would read $\{x:x∈L_1∨x∈L_2\}$ as "the set of strings such that the string is in $L_1$ or the string is in $L_2$."

This does NOT mean that for any string $s∈L_1$, we also have $s∈L_2$.

We only have that for any string $s$ in the union of languages $L_1$ and $L_2$, denoted $s \in (L_1\cup L_2$), that string $s$ is in either $L_1$ or $L_2$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thank you for the clarification. By "the union of two regular languages is also a regular language", this means we can construct a DFA that accepts the union of L_1 and L_2, correct? (as per definition of regular language) $\endgroup$
    – socrates
    Commented Oct 2, 2016 at 20:50
  • $\begingroup$ Yes, if a language is regular then we can always construct some DFA that only accepts the strings of that language. For a description of how one might construct the DFA that accepts the union of two regular languages see this post: cs.stackexchange.com/questions/22000/… $\endgroup$
    – ctj232
    Commented Oct 2, 2016 at 20:52
  • $\begingroup$ Thank you so much. As you can tell, the question you linked is the direction I'm headed in. The one question I have is: my instructor defined the union of two DFA's as: M=(Q1×Q2,Σ,δ,(s1,s2),F1×F2). The question assumes F1×F2 = {x | x in F1 or x in F2). Is this the standard way to define (F1, F2)? $\endgroup$
    – socrates
    Commented Oct 2, 2016 at 21:07
  • $\begingroup$ And, as a follow up, for M' a DFA that simulates two DFA's, M_1 and M_2, would M' accept prefix-free languages iff, for $F1 \in M_1$ and $F2 \in M_2$, and for $\delta_1 \in M_1$, and $y \in L_2 (L(M_2) = L_2)$, $\delta_1(F_1,y) \not \in F2$? $\endgroup$
    – socrates
    Commented Oct 2, 2016 at 21:11
  • 1
    $\begingroup$ @socrates. Your instructor is using what's known as the product construction for two FAs, as in these notes. That's a perfectly good way to do it, but you can also use regular expressions or finite automata with epsilon-moves. If you haven't heard of these, you will soon. $\endgroup$
    – Rick Decker
    Commented Oct 2, 2016 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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