Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (40.65 KiB) Viewed 57 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
Theory of Computation.
Please type your solution very clearly
1. This problem is based on problem 7.6 in Sipser. We will prove that P is closed under complement, union, intersection, and concatenation. Formally, let L1, L2 be formal languages with L1, L2 E P - that is, both languages can be recognized in polynomial time (a) (5 points) Prove that L1 = {w\w & Li} E P (b) (5 points) Prove that Lį U L2 = {W/W E Lį or w E L2} E P (c) (5 points) Prove that Li oL2 = {w/w = xy for some x e L1, y € L2} € P = = = =
Please type your solution very clearly
1. This problem is based on problem 7.6 in Sipser. We will prove that P is closed under complement, union, intersection, and concatenation. Formally, let L1, L2 be formal languages with L1, L2 E P - that is, both languages can be recognized in polynomial time (a) (5 points) Prove that L1 = {w\w & Li} E P (b) (5 points) Prove that Lį U L2 = {W/W E Lį or w E L2} E P (c) (5 points) Prove that Li oL2 = {w/w = xy for some x e L1, y € L2} € P = = = =