Prove that the family of regular languages is closed under the operation of set difference.
(I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the transition function.)
Asked
Active
Viewed 1,912 times
0
-
1What closure properties of the class of regular languages do you know? – PhoemueX Mar 18 '16 at 21:54
-
@bambam Please explain how you attempted to solve the problem? This will prevent people from downvoting your post. – Arbuja Mar 18 '16 at 21:55
-
@Arbuja I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the transition function. – zxccxz Mar 18 '16 at 21:57
-
@bambam Be sure to include this in your original post. More people will try and answer your question. – Arbuja Mar 18 '16 at 21:59
-
@PhoemueX union, concatenation and Kleene star – zxccxz Mar 18 '16 at 22:00
1 Answers
1
From set theory we get $$ L_1 \setminus L_2 = L_1 \cap L_2^c $$
So you can reduce this problem to closure of regular languages regarding set intersection and set complement.
Regularity of $L_1 \cap L_2$ should follow from product automaton construction from a DFA for $L_1$ and $L_2$ each.
Set complement should follow from taking a DFA for $L_2$ and turning final states into normal states and vice versa.
mvw
- 34,562