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?

  • 1
    $\begingroup$ I'm fairly sure we already have this on the site somwhere. Also, related question. $\endgroup$
    – Raphael
    Feb 7 '18 at 18:54
  • $\begingroup$ @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? $\endgroup$
    – Meik Vtune
    Feb 7 '18 at 19:25
  • $\begingroup$ cs.stackexchange.com/questions/33853/… describes an approach. $\endgroup$
    – rici
    Feb 7 '18 at 19:30
  • $\begingroup$ @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}$ $\endgroup$
    – Meik Vtune
    Feb 7 '18 at 19:54
  • $\begingroup$ @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! $\endgroup$
    – Raphael
    Feb 7 '18 at 20:47