1
$\begingroup$

Below is a saying from this article.

Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the strings matched by the expression. But, the reverse is not true: not every grammar can be converted into an equivalent regular expression.

Can anyone tell me if the saying is correct and why? Per my understanding, they should have same power and the differernce is a context-free grammar has recursive definition.

$\endgroup$
1
$\begingroup$

Let the set of languages that can be represented by regular languages be $R$. And set of languages that can be generated by a context free grammar be $G$. Then surely $ R \subset G$. For the proof that every regular language has a context free grammar that generates it, I encourage you to look up Michael Sipser's book on complexity. And for the second part, there are many languages which have a context free grammar generating them but are not regular. For example $L=\{ww^{reverse}\}$, where $w^{reverse}$ is reverse of the string $w$. How do we know $L$ has a context free grammar ( you can easily come up with a push down automata for it ), look up Sipsers. And look up pumping lemma in the book to prove $L$ is not regular.
To get an intuition, any regular language can be represented by a finite state automata $FSA$ and vice versa. And any context free grammar can be represented by a push down automata $PDA$ and vice versa ( again read the proof from Sipsers ). And in a $PDA$ in addition to the states ( like in $FSA$ ) you also have an infinite memory stack. Thus intuitively context free grammars have "power" greater than that of $FSA$.

$\endgroup$
  • $\begingroup$ Thank you, Sasha. I will follow your guide and dig more. $\endgroup$ – appleleaf May 9 '16 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.