0

I'm asked to show that the set of songs of the form ABA^R is context-free(where A^R is A reversed). I don't know how to show a language is context-free.

We haven't studied specifically how to show that a language is context-free so it can't be too complicated. The only thing I can think of is making a context-free grammar for the language but I don't really know if that's sufficient to show that it is context-free or how I'd make a grammar for a set of songs.

jtht
  • 793
  • 2
  • 10
  • 19
  • There is an answer here: http://stackoverflow.com/questions/3510109/how-can-i-determine-if-a-language-is-context-free-or-not Also note that creating context-free grammar is fine for showing a language is context free. – Spencer Wieczorek Sep 26 '14 at 04:21
  • You cannot use pumping lemma to show a language is context free. It can only be used to show it is not. There are non-context free languages which satisfy the pumping lemma. – Nuri Tasdemir Sep 26 '14 at 04:23
  • Are A and B set of strings or what? – Nuri Tasdemir Sep 26 '14 at 04:24
  • @NuriTasdemir Yeah I guess. This is all the information I have. Guess I'll try to make a grammar for it. – jtht Sep 26 '14 at 04:26
  • Use `push down automata`. But what do you mean by `A^R` is `A` reverse. Can you be more specific – nu11p01n73R Sep 26 '14 at 04:27
  • It's important to know what A and B are in this formulation. If each is simply any string over a given alphabet (i.e., the same alphabet for both), then you don't need to construct a CFG for the language, you can just reason it out. (Hint: "any string" could be the empty string.) – Michael Dyck Sep 26 '14 at 17:26

1 Answers1

0

Assuming A and B are set of strings and they are Context Free, then there are context free grammars for language A and B, say G_A and G_B. You can obtain the context free grammar for language A^R from G_A, quite easily. Just reverse the right hand side of the grammar rules and voila you have the grammar for A^R.

If the starting variable of G_A is S_A, G_B is S_B and G_A^R is S_A' then the final grammar will be the combination of these grammars (each variable of the three grammar should be named uniquely) with the new starting variable and the new rule stating

S -> S_A S_B S_A'
Nuri Tasdemir
  • 9,720
  • 3
  • 42
  • 67
  • In deriving a sentence ("song") from your S, S_A' is not constrained to derive a phrase that is the reverse of what S_A derives, which I think is what the original question requires. – Michael Dyck Sep 26 '14 at 17:21
  • @MichaelDyck S_A derives a string from A and S_A' derives a string from A^R. Those two string may not be the reverse of each others and that is intentional. That is what the OP asks. If those should be the reverse of each other (I take it you think this way) then question should be asked as L = {xyx^R| x \in A AND y \in B} – Nuri Tasdemir Sep 26 '14 at 19:48