-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$
  • 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 'SO- stop being evil' 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.