Page 1 of 1
10. (10 pts) Let I = (u € (0.1}whas the same number of O's and 1's). Consider the fol- lowing algorithm that decides L.
Posted: Sat May 14, 2022 7:26 pm
by answerhappygod
- 10 10 Pts Let I U 0 1 Whas The Same Number Of O S And 1 S Consider The Fol Lowing Algorithm That Decides L 1 (27.42 KiB) Viewed 36 times
10. (10 pts) Let I = (u € (0.1}whas the same number of O's and 1's). Consider the fol- lowing algorithm that decides L. 17 = "In input 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 I or is found 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