regexgrammarautomata

Convert regular expression to CFG


How can I convert some regular language to its equivalent Context Free Grammar? Is it necessary to construct the DFA corresponding to that regular expression or is there some rule for such a conversion?

For example, consider the following regular expression

01+10(11)*

How can I describe the grammar corresponding to the above RE?


Solution

  • and proceed recursively on A and B. Base cases are empty language (no productions) and a single symbol.

    In your case

     A -> 01
     A -> 10B
     B -> (empty)
     B -> 11B
    

    If the language is described by finite automaton: