What is the language generated by this grammar?

Question

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

Any help would be appreciated.

Answer 1

Let's analyze this step by step. I. Let's suppose we chose the first production from the axiom: $$ S \to P$X $$ 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: $$ w$w^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 aaba$abaa $$ 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: $$ w$w^R$x \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 X$bTa$$ 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^n$a^n \text{, where } n \text{ is a whole number or zero.} $$ Summing this branch up, we get: $$ x$bb^n$a^na \text{, where } x \in \{a,b\}^* \text { and } n \text{ is a whole number or zero,} $$ which is identical to: $$ x$b^n$a^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 = \{w$w^R$x \mid w, x \in \{a, b\}^* \text { and } w^R \text{ is the reversed } w\} \text { } \text{ } \text{ }\cup \{x$b^n$a^n \mid x \in \{a,b\}^* \text { and } n \text{ is a whole number}\}.$$

The problem situation might seem scary and/or unwieldy, yet a coherent step-by-step analysis always does the trick.

I hope I did not make any mistakes in my solution.

I can recommend some literature on the topic: "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman; "Algorithms and Programming. Problems and Solutions" by A. Kh. Shen and "The Mathematical Theory of Context-Free Languages" by S. Ginsburg.