# What is the language generated by this grammar?

I'm struggling to find the language generated by the following grammar:

Any help would be appreciated.

• What progress have you made? Can you define the language generated by $X$? by $T$? by $P$? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Mar 27 at 2:20
• i found that L = {b^n $b^n$ a^n | n in N+} but i'm not sure – louis_02 Mar 27 at 2:32
• Please don't add clarifications in the comments; edit your question. Don't guess -- prove your answer. See for example cs.stackexchange.com/q/11315/755. Proof-read your typeset output to make sure it matches your intent. Use Latex for mathematics; see here for a short introduction. – D.W. Mar 27 at 3:31

Let's analyze this step by step. I. Let's suppose we chose the first production from the axiom: $$S \to PX$$ Here we encounter two new non-terminals (some call them variables. The reception of non-terminal symbols as some "entities" in the language comes in pretty handy during one's first steps into the formal grammar theory, yet it is imperative, from my point of view, to understand that at the end of the day they are just symbols. The term "non-terminal" implies that unlike the term "variable"): P and X. It is kind of no use to compose separate branches for them as they are recursive and it would lead to a pretty cumbersome solution. It is easier to analyze the ulterior meaning behind those symbols via looking at the productions (again): $$P \to aPa \mid bPb \mid$$ It is easy to see that this non-terminal generates a substring of the following structure: $$ww^R \text{, where } w \in \{a, b\}^* \text { and } w^R \text{ is the reversed } w.$$ Let's try writing a chain of relations down in order to illustrate our result: $$P \Rightarrow aPa \Rightarrow aaPaa \Rightarrow aabPbaa \Rightarrow aabaPabaa \Rightarrow aabaabaa$$ Now, let's move on to X. X does an even simpler thing - it generates $$\{a, b\}^*$$. E.g.: $$X \Rightarrow bX \Rightarrow baX \Rightarrow baaX \Rightarrow baabX \Rightarrow baabbX \Rightarrow baabb$$ Summing this branch up, we get the following structure: $$ww^Rx \text{, where } w, x \in \{a, b\}^* \text { and } w^R \text{ is the reversed } w.$$
Now, we shall proceed to the second possible production from the axiom: $$S \to XbTa$$ We already know what X does, so the only missing part of the puzzle at this point is the non-terminal T: $$T \to bTa \mid$$ Once again, the generated structure is pretty neat: $$b^na^n \text{, where } n \text{ is a whole number or zero.}$$ Summing this branch up, we get: $$xbb^na^na \text{, where } x \in \{a,b\}^* \text { and } n \text{ is a whole number or zero,}$$ which is identical to: $$xb^na^n \text{, where } x \in \{a,b\}^* \text { and } n \text{ is a whole number.}$$ Thus, the language couldbe written down as the following union: $$L_G = \{ww^Rx \mid w, x \in \{a, b\}^* \text { and } w^R \text{ is the reversed } w\} \text { } \text{ } \text{ }\cup \{xb^na^n \mid x \in \{a,b\}^* \text { and } n \text{ is a whole number}\}.$$