3 ms·
That requires you to have the entire string in memory, so it’s still Ω(n). Regular languages can be recognized using O(1) space and a single reading pointer in
by pwdisswordfish9 5y ago
That requires you to have the entire string in memory, so it’s still Ω(n). Regular languages can be recognized using O(1) space and a single reading pointer into the string, without even storing it whole; you can process it in a streaming manner.