CODEWITHSUNDEEP
context-free-grammar
Ponty
Ponty

Reputation: 645

How to find the language generated by a CFG

If a Context-Free Grammar is given, is there a systematic way to find out the generated language and express it as a set using a descriptive and not analytic way, like L(G)={0^n.1^n|n?=1} (and not L(G)={01,0011,000111,...}) ?

I actually ask because if a CFG is given and there is a question like: "Find the language of the grammar.Prove/Justify your answer." , then how can someone prove/justify his/her answer otherwise?

Upvotes: 1

Views: 2560

Answers (1)

Jim Lewis
Jim Lewis

Reputation: 45035

In general, no. For example, for an arbitrary context free grammar, the question of whether the language is equivalent to Sigma* is undecidable -- and that's about the simplest description of a CFL one might imagine. Another undecidable question is whether two context free grammars A and B define the same language, which doesn't bode well for the more general question of whether a grammar and some other alternate presentation define the same language.

In specific cases, such questions may be decidable -- fortunately for formal language theory students! But in light of the above decidability results, you're not going to find a simple algorithm that gets you from a grammar, to a concise description of the sort usually presented in language theory textbooks. It's more of a trial and error process, where you use some intuition to think up a candidate description, then apply the more formal methods like building parse trees, or using closure properties or pumping lemmas, to prove or disprove the equivalence.

Upvotes: 3

Related Questions