Given the alphabet $Λ = \{a, b\}$ and this non-regular language:


what's the best way to generate the grammar? Every string has to start with $ab$, then we have $aba$ and this part has to have the same number of $a$. In words that is clear, but I'm stuck; should I first consider the fixed part $ab$, or is better to produce the $a^nb^ma^n$ part and then add the $ab$? I need a method basically.

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 26 '17 at 21:06

You should think of this language as all words of the form $$ xa^nya^n, $$ where $x=ab$ and $y \in b^*$. You can now modify a grammar for $a^nb^n$ to generate your language.


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.