Page 1 of 1
10. (10 pts) Let I = {w = {0.1} has the same number of O's and 1's). Consider the fol- lowing algorithm that decides L.
Posted: Sat May 14, 2022 7:32 pm
by answerhappygod
- 10 10 Pts Let I W 0 1 Has The Same Number Of O S And 1 S Consider The Fol Lowing Algorithm That Decides L 1 (28.45 KiB) Viewed 38 times
10. (10 pts) Let I = {w = {0.1} has the same number of O's and 1's). Consider the fol- lowing algorithm that decides L. M = "In inputs 1. Scan across the tape until a 0 or 1 is found. 2. If none is found, accept. 3. If one is found, continue scanning until a matching 1 or 0 is found. 4. If none is found, reject. 5. Otherwise, cross off that symbol and repeat. Using the Big-O notation, state the time complexity of each step of M, and the overall time complexity of M.