Когда мы ко­пи­ру­ем стро­ку, нам важно по­ни­мать, какие эле­мен­ты мы уже ско­пи­ро­ва­ли, а какие ещё нет. По­это­му уже ско­пи­ро­ван­ные еди­ни­цы мы будем «по­ме­чать» ис­поль­зуя для этого вспо­мо­га­тель­ный сим­вол 2.

Как ра­бо­та­ет наша ма­ши­на:

а)  Так   — если мы встре­ча­ем еди­ни­цу в на­чаль­ном со­сто­я­нии, мы за­ме­ня­ем её на двой­ку и на­чи­на­ем дви­же­ние на­пра­во.

б)  Так   — эти пра­ви­ла от­ве­ча­ют за дви­же­ние управ­ля­ю­ще­го эле­мен­та на­пра­во до вто­рой встре­чен­ной звез­доч­ки (когда мы встре­ча­ем первую звез­доч­ку, это от­ме­ча­ет­ся пе­ре­хо­дом из со­сто­я­ния q1 в со­сто­я­ние q2.

в)  Так   — мы на­хо­дим вто­рую звёздоч­ку, за­ме­ня­ем её на еди­ни­цу и на­чи­на­ем дви­же­ние на­ле­во.

г)  Так   — ана­ло­гич­но преды­ду­щей груп­пе пра­вил, дви­жем­ся на­ле­во до тех пор, пока не встре­тим двой­ку. Встре­тив двой­ку, мы воз­вра­ща­ем­ся в на­чаль­ное со­сто­я­ние s и на­чи­на­ем ис­кать сле­ду­ю­щую еди­ни­цу. Если мы её нашли, мы воз­вра­ща­ем­ся об­рат­но к пер­во­му пра­ви­лу и по­вто­ря­ем про­цесс за­но­во. Если сле­ду­ю­щая еди­ни­ца не об­на­ру­же­на, вы­пол­ня­ет­ся пра­ви­ло   — про­цесс ко­пи­ро­ва­ния окон­чен, но все ис­ход­ные еди­ни­цы у нас за­ме­не­ны двой­ка­ми, и надо вер­нуть их в ис­ход­ное со­сто­я­ние. Это де­ла­ет­ся при по­мо­щи пра­ви­ла На­ко­нец, когда мы в со­сто­я­нии встре­ча­ем звёздоч­ку, пра­ви­ло го­во­рит нам за­кон­чить ра­бо­ту.

Ответ: см. рис.