# Grammar/Chomsky-Type for $L = \{ww \mid w \in \{a,b\}^*\}$ [duplicate]

I've been given the following task and have tried a few things, but none seem to result in what is required.

$L = \{ww \mid w \in \{a,b\}^*\}$

What Chomsky-Type is $L$? Provide a grammar fulfilling that Type.

It can't be context-free, since that wouldn't allow us to force that we write each symbol twice at the right place. Also it shouldn't be Type-0, since I suspect that rules that satisfy context-sensitive should be fine(namely all rules fulfill $u \rightarrow p$ with $\mid u\mid \leq \mid p\mid$)

Now I've tried to find a working grammar that fulfills Type-1, but I fail at getting the right order of $a,b$ in the second word.

How could I go about this and am I even right with suspecting to be able to find a Type-1 grammar?

• I'm fairly sure we already have this on the site somwhere. Also, related question.
– Raphael
Feb 7 '18 at 18:54
• @Raphael That's an awesome topic, thank you. Since the accepted answer is of a TM, I suspect that my assumption that $L$ is of type-1 is false, else they'd use a pushdown automaton, right? Feb 7 '18 at 19:25
• cs.stackexchange.com/questions/33853/… describes an approach.
– rici
Feb 7 '18 at 19:30
• @rici Thank you so much, that is a great answer, very generic for any Language $L$ with $\{w^k \mid w \in \Sigma^* \} \forall k\in\mathbb{N}$ Feb 7 '18 at 19:54
• @rici Note that LBAs are eqivalent to type-1, not TMs. Try to figure out if you can implement Klaus Draeger's sketch wthout using additional tape!
– Raphael
Feb 7 '18 at 20:47