I need to Find grammar for the following language: $\{ a^{m_1}ba^{m_2}b\dots a^{m_k}bca^n \mid m_j = n \text{ for some } 1 \le j \le k \}$.

can someone help me to solve it? I am not sure how to start.

  • 3
    $\begingroup$ What did you try? Where did you get stuck? If you can't even start, you need to review your course materials, textbook and so on. Producing a grammar for any given language is a creative act: you can't just expect to follow some recipe. $\endgroup$ – David Richerby Jan 15 '17 at 16:57

First try to understand the form of the strings in the language. If $m_j=n$ then strings are of the form $\dots a^n b \dots c a^n$. What is on the place of the dots?

  • $\begingroup$ I understand that but i don't understand how i make the a^n to be equal to the a^mj $\endgroup$ – user64211 Jan 15 '17 at 16:31
  • $\begingroup$ I guess you can make a grammar for $\{a^nba^n\mid n\ge1\}$. $\endgroup$ – Hendrik Jan Jan 15 '17 at 20:45
  • 1
    $\begingroup$ Cute. We all understand that you meant to write $\dotsc a^n\dotsc ca^n$ in your answer. $\endgroup$ – Rick Decker Jan 15 '17 at 21:16

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.