correct and proven!
- Help Needed Please I Will Thumbs Up Asap If Everything Is Correct And Proven 1 (168.43 KiB) Viewed 22 times
Help Needed Please - I will thumbs up ASAP if everything is correct and proven!
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Help Needed Please - I will thumbs up ASAP if everything is correct and proven!
Help Needed Please - I will thumbs up ASAP if everything is
correct and proven!
2. (Time complexity, 20pt) For the following languages, sketch (high-level, no need to mention states) a 1-tape TM program that solves the problem and include a time analysis of your program showing how much time it takes, e.g. O(n),O(nlog n), O(n2), O(n3), etc.; n is the length of the input. = a) [10pt] L = {u#v: U, v E {0,1}* and u is a substring of v} b) [CSC 389, 10pt] L = {02%: for k > 03. E.g. 0,00,0000,00000000 € L. Note that n = = 2k.
correct and proven!
2. (Time complexity, 20pt) For the following languages, sketch (high-level, no need to mention states) a 1-tape TM program that solves the problem and include a time analysis of your program showing how much time it takes, e.g. O(n),O(nlog n), O(n2), O(n3), etc.; n is the length of the input. = a) [10pt] L = {u#v: U, v E {0,1}* and u is a substring of v} b) [CSC 389, 10pt] L = {02%: for k > 03. E.g. 0,00,0000,00000000 € L. Note that n = = 2k.