Skip to content

Instantly share code, notes, and snippets.

@QwertyJack

QwertyJack/p1

Created September 16, 2020 10:24
Show Gist options
  • Save QwertyJack/4139cde75cce0ac7371f227e2d57a89d to your computer and use it in GitHub Desktop.
Save QwertyJack/4139cde75cce0ac7371f227e2d57a89d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
p1
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