Mängder

Hej!

Jag läser just nu automatateori och här är en uppgift angående mängd jag inte förstår:

Beskriv mängden på ett mer direkt sätt:
{w | w=ww}

Svar:

Varför blir det så? Vad betyder tecknet | ?

EDIT

Jag tror att jag förstår:
Uttrycket betyder att mängden beskriver alla strängar w, som uppfyller kriteriet att två strängar efter varandra är lika stora som en, då är det bara den tomma strängen som passar...

"Efter varandra"? Borde det inte då innebära w+w, istället för ww?

Alltså;

{w | w=w + w}

istället för

{w | w=ww}, vilket jag tolkar som
{w | w=w*w}

w=0 borde ju fungera ändå, men om det är multiplikation som avses, så är ju w=1 också en lösning och den mängden skulle då innehålla ett element (talet 1).

Jag är ganska säker på att du har förstått korrekt.

Du har förstått rätt! "|" utläses "sådant att". Konkatenering av strängarna a och b skrivs helt enkelt "ab", så mängden vi söker kan med ord skrivas som "mängden av alla strängar w sådana att w konkatenerat med sig själv blir w". Uppenbarligen är söker vi tomma strängen, så alla strängar av positiv längd blir dubbelt så långa efter konkatenering med sig själv.

Notera vidare att {epsilon} inte är en tom mängd, det är en mängd som innehåller precis ett element, nämligen tomma strängen.

Tack för svaren!

Här är en uppgift till på samma ämne som jag inte förstår:

Hitta mer direkt beskrivning för: {w | w=uu^rev för någon sträng u över Zigma}

Så som jag fattar det så delar man upp strängen w i två bitar u och u. Då ska det sista u:et reverseras och strängen ska fortsätta vara lika. Så ifall w består av två palindrom (u) så borde det gälla.
Jag förstår inte vad "för någon sträng u över Zigma" innebär.

Mitt resonemang är inte riktigt rätt, här är svaret:
Kan någon förklara?

Uppenbarligen söker du palindrom (där ett palindrom definieras som en sträng som är identisk med strängen baklänges om man läser tecken för tecken). Vidare ser vi att bara palindromen av jämn längd fungerar, då de av udda längd inte kan delas upp i två lika långa strängar.

Ditt resonemang att w ska bestå av två palindrom täcker bara en delmängd av lösningarna eftersom till exempel abccba, som är en sträng över alfabetet {a, b, c} uppenbarligen uppfyller villkoret men inte består av två palindrom. Däremot har du lyckats få med några av lösningarna i ditt svar, då alla konkateneringar av två palindrom är ett palindrom.

Sigma brukar beteckna alfabetet man har. Ett alfabet är en uppsättning tecken som du kan bygga strängar av. Exempel på alfabet är {a, b, c}, {0, 1}. En sträng över sigma där sigma är ett alfabet betyder helt enkelt en sträng där samtliga tecken finns i alfabetet.

Men det jag inte förstår är detta, som jag förmodligen har fått om bakfoten:

Om jag har strängen w = abcddcba så blir väl uu^rev = abcdabcd, eller? blir inte första u första halvan av strängen och andra u andra halvan?

Om w=abcddcba=uu^rev så är u=abcd och u^rev=dcba. Vi ser att denna sträng fungerar för detta alfabet.

Aha! Det där förstod jag.