-1
$\begingroup$

This is the problem: http://i.imgur.com/Io7h1en.png

This was a problem I saw and I really have 0 clue what the Language means the (**) part, and its solution.

I was wondering if anyone could please help me?

I do know what grammars are and how to read them, but this one was confusing and what I really want to know is how one would approach a problem like this. If I was given this problem, I wouldn't even know where to start.

Thank you.

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by David Richerby, Hendrik Jan, Gilles Apr 21 '16 at 8:38

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I've no idea what $**$ means, either: it should have been defined earlier in whatever document you took the question from. Otherwise, you seem to be asking "How can I find a grammar for an arbitary given language." That's a very broad question to which the only real answer is "Check the textbooks for general advice and then get lots of practice." Finding things like grammar and automata is essentially a creative act. If there was a straightforward recipe, we'd have programmed that into a computer by now. $\endgroup$ – David Richerby Apr 20 '16 at 22:12
  • 1
    $\begingroup$ @David Richerby Unfortunately, the ** wasn't defined anywhere I searched. Perhaps it means a^(n^2)? But, could you explain how you would approach this problem itself? $\endgroup$ – Sam is the Man Apr 20 '16 at 22:53
  • $\begingroup$ Possible duplicate of Grammar for square numbers in unary $\endgroup$ – Hendrik Jan Apr 20 '16 at 23:22
  • 1
    $\begingroup$ Don't post an image and expect us to decipher it. $\endgroup$ – Gilles Apr 21 '16 at 8:39
3
$\begingroup$

The notation ** is an old way of writing exponentiation ^.

The grammar is a type-0 grammar, where any string can be replaced by another. It actually comes close to a context-sensitive grammar (or better monotonous grammar) except for the last three productions.

Generating squares is usually done using the recurrence $(n+1)^2 = n^2 + 2n +1$ so the strings always contain a $n$ specially distinguished symbols so one can add the double amount of $2n$ to get the next square. After adding 1 of course.

Here I guess this is seen in the production $M_R A \to aA M_R$: the symbol $M_R$ moves over the string and adds an $a$ for each $A$.

|cite|improve this answer
$\endgroup$

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