i am trying to understand Context free grammar and generate a CFG for any given language.

when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow to help you create a CFG for any language? is there ways of breaking down the language to make it simpler so that it helps you generate the CFG.

for example if i was given L={a^n (ba)^m a^n | n,m >=0 }

does that mean i need to have equal number of a's on both side, and have zero or more ba in between the a's ?

S---> aSa |ε

X---> baX |ε

any helps is appreciated.

  • 5
    $\begingroup$ Possible duplicate of How to prove that a language is context-free? $\endgroup$ Dec 17 '18 at 23:44
  • $\begingroup$ my question is not about whether the language is context free or not. i am just finding it difficult give a CFG for any given language. there must be a way of breaking down languages into smaller parts to make it easy when generating a CFG for it. that is what i am asking here. and i want to understand it by going through some examples with people who know it well. $\endgroup$ Dec 17 '18 at 23:51
  • $\begingroup$ I think my cfg was not working . and i come up with a better answer , which i think it is working : S ----> aSa | X X ----> baX | ε $\endgroup$ Dec 17 '18 at 23:52
  • $\begingroup$ well, in an answer to the "How to prove ..." reference question it is explained that the grammar can indeed be made from standard components once the "nesting structure" of the strings is found. In your case the nesting is from the outside, so I would start with $S\to a S a$. $\endgroup$ Dec 17 '18 at 23:58
  • $\begingroup$ @Hendrik Jan thanks for your hints and answer, "Nesting" , that is the sort of answer i was looking for . can you please elaborate on that more in relation to the language or any other language. how does that work? and yes as for my previous answer . i came up with a different solution which is : S ----> aSa | X X ----> baX | ε $\endgroup$ Dec 18 '18 at 0:07

The reference question "How to prove that a language is context-free?" has some examples to build a context-free grammar using a simple toolbox. As is mentioned there one needs a "nesting structure" to make this work.

You ask about the difference between language like $L_1 = \{ab^na^nc \mid \dots \}$ and $L_2 = \{a^n (ab)^m a^n \mid \dots \}$. In both cases the parts that are iterated the same $n$ number of times have to be generated in parallel. Productions like $Y\to b Y a$ are good for that.

In case of $L_1$ the $a\dots c$ pair is around the repeat $b^nc^n$ and can be generated before $S\to a X c$, but also independently as $S\to AXC, A\to a, C\to c$ . In case of $L_2$ the $(ab)^m$ is inside the repeat $a^n\dots a^n$ and has to be generated after, like your own solution $S\to aSa, S\to X, X\to abX\mid \varepsilon$.

  • $\begingroup$ Thank you so much for your clarification and further assistant. as a student with "Learning Difficulty" , i can say that this has made the concept easier to understand. and makes more sense now. based on this , now i can structure & break down languages into smaller parts to help me generate appropriate CFG. so for L1 , i now have : S -----> aSc | X X---->bXa | ε . $\endgroup$ Dec 18 '18 at 14:46
  • $\begingroup$ @RickDecker i think you're looking at L2 right ? the cfg is generated for L1, so the X ---> bXa is for b^n a^n part in L1 . $\endgroup$ Dec 18 '18 at 16:06
  • $\begingroup$ @chelseablue Ah, I see. You're right, of course. $\endgroup$ Dec 18 '18 at 23:56
  • $\begingroup$ @RickDecker , just to confirm is my cfg S -----> aSc | X X---->bXa | ε totally correct for language L1={a b^n a^n c | n>=0} ? $\endgroup$ Dec 19 '18 at 12:38
  • $\begingroup$ @chelseablue Not quite. Your grammar would generate $aabbaacc$, which isn't in $L_1$. Try $S\rightarrow aTc, T\rightarrow bTa\mid\epsilon$. $\endgroup$ Dec 19 '18 at 16:13

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.