Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
Asked By : Marco L.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9050
Answered By : Raphael
I assume you want to get a grammar that generates the same language as the given regular expression.
You can achieve that by the following steps:
- Translate the regular expression into an NFA.
- Translate the NFA into a (right-)regular grammar.
Both translations are standard and covered in basic textbooks on formal languages and automata. Note that any regular grammar is also context-free.
Post a Comment