Page 1 of 1
2. (10 pts) Let L = {w € {a,b}\whas the same number of a's and b's). Consider the fol- lowing algorithm that decides L.
Posted: Sat May 14, 2022 7:38 pm
by answerhappygod
- 2 10 Pts Let L W A B Whas The Same Number Of A S And B S Consider The Fol Lowing Algorithm That Decides L 1 (27.97 KiB) Viewed 28 times
2. (10 pts) Let L = {w € {a,b}\whas the same number of a's and b's). Consider the fol- lowing algorithm that decides L. 1/ = "In input w: 1. Scan across the tape until a a or b is found. 2. If none is found, accept. 3. If one is found, continue scanning until a matching b or a is found. b 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 tir complexity of M.