1
$\begingroup$

Is there a general rule to convert a CFG to its CFL?

For example, how do I approach the following question?

What is the language generated by the following CFG? $$ S \to aS \mid Sb \mid \epsilon $$

As per my understanding, $S\to aS$ is $a^*$ and $S\to Sb$ is $b^*$.

But how do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?

In particular, is there a way to make it either in left or right recursion, so that it is easier to understand the structure?

$\endgroup$
2
  • 1
    $\begingroup$ In mathematics, the way to know things for sure is to prove them. $\endgroup$ Nov 29, 2020 at 11:49
  • $\begingroup$ (Is a regular expression a language any more than a grammar is?) $\endgroup$
    – greybeard
    Nov 29, 2020 at 13:30

1 Answer 1

1
$\begingroup$

Is there a general rule to convert a context-free grammar to a context-free language?

The answer depends on what you mean by "context-free language". A context-free grammar is one way to describe context-free languages, so in some sense the answer is a trivial "yes" – a context-free grammar is already a description of a context-free language.

Presumably you are interested in a more explicit description. In this case, the answer is probably "no", though it's impossible to tell unless you define your problem formally. The reason for the negative answer is the following undecidability result: given a context-free grammar over an alphabet $\Sigma$, determining whether it generates $\Sigma^*$ is undecidable.

How do I make sure that the language is $a^* b^*$ without having to derive a lot of strings?

In mathematics, the way to know things for sure is to prove them.

Is there a way to make it either in left or right recursion so that it is easier to understand the structure?

If a grammar contains only left-recursion or only right-recursion, then it is a left-regular grammar or a right-regular grammar, respectively (actually, whether this is true depends on what you mean by left-recursion and right-recursion, so I am making a guess). (Another common term is left-linear/right-linear grammar.) Such a grammar generates a regular language. Given that it is undecidable whether a given context-free grammar generates a regular language, there is no simple transformation that can change an arbitrary context-free grammar into one with only left-recursion or only right-recursion.

A grammar mixing left-linear and right-linear rules is known as linear; such grammars describe linear languages, a sub-class of all context-free languages which contains non-regular languages such as $\{a^nb^n \mid n \geq 0\}$, generated by $S \to aT \mid \epsilon, \, T \to Sb$.

It seems that even determining whether a given linear grammar describes a regular language is undecidable, see the comments to this answer by J.-E. Pin.

$\endgroup$
1
  • $\begingroup$ Thank you ! I have been trying to convert CFG to RE and almost all questions I have done contained either left or right linear grammar but not both . So it has always been Production rule->DFA->RE ; now as I understand by reading your answer ,I shouldn’t solely rely on that method (somehow I forgot that the latter approach won’t work with Non Regular Language ) $\endgroup$
    – leena
    Nov 29, 2020 at 19:16

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.