-
-
Save QwertyJack/4139cde75cce0ac7371f227e2d57a89d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
P1. | |
Let A is the former and B is the latter. | |
(a) No. r1r1r1r1r2r1 is in B but not in A. | |
(b) No. r1r2r2 is in A but not in B. | |
(c) No. empty string is in B but not in A. | |
(d) Yes. A is all strings that contains at least one r2 or one r1; B is the same. | |
(e) Yes. Let's prove all strings s is in A. Consider the length of the string `s`: | |
0: s = empty. s is in r1*r2* obviously. | |
1: s = r1 or s = r2. s is in r1*r2* obviously. | |
>=2: if s contains both r1 and r2, then s must contains r2r1 or r1r2, so s is in A. | |
if s contains only r1 or only r2, then s is in r1*r2*. Also s is in A. | |
(f) Yes. r1* is contained in (r1 + r2)*, so that B contains A. Let's prove A contains B, | |
which is all stirngs s that contains at least one r2. Consider the first place X in s where | |
s2 occurs, then location [0, X) in s must be s1, so that s[0, X] is in r1*r2, then s is in A. | |
(g) No. r2r2 is in A not in B. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment