Prove or disprove (L1 ∪ L2)R = L1R ∪ L2R for all languages L1 and L2.
Note: The R superscript stands for "reverse".
Now, I'm not the best at proofs which is why I'm coming here. I "think" I've figured it out, but it just seems to easy. I feel like I must be missing something, or I'm assuming something that isn't actually valid in this scenario.
This is what I have:
The left side of the equation says (L1 ∪ L2)R. By DeMorgan's we know this is equal to L1R ∩ L2R.
However, the right side implies that this equals L1R ∪ L2R. This is incorrect due to DeMorgan's. Disproved.
Is it really this simple? Does DeMorgan's apply to languages like this? If I'm thinking about this completely wrong could someone get me on the right track?
This post has been edited by eZACKe: 03 February 2011 - 01:00 PM