I'm struggling to find the language generated by the following grammar: enter image description here

Any help would be appreciated.

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 27, 2020 at 2:20
  • $\begingroup$ i found that L = {b^n $ b^n $ a^n | n in N+} but i'm not sure $\endgroup$
    – louis_02
    Mar 27, 2020 at 2:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 27, 2020 at 3:31

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.