How do I check wether a string is generated by given regular grammar?I know you can check for it in O(N), what is the algorithm called?
checking if string is generated by regular grammar
regular languages
A regular grammar corresponds quite closely to a non-deterministic finite automaton, reading the word in the usual way (right regular grammar) or backwards (left regular grammar). You can run $m$-state NFAs on inputs of length $n$ in complexity $O(2^m n)$, which is linear if you fix the NFA.