World's most popular travel blog for travel bloggers.

[Solved]: checking if string is generated by regular grammar

, , No Comments
Problem Detail: 

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?

Asked By : lllook

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback