Oefenzitting 4 oefening 3 nummer 4

[warreee]

In de opgave staat dat er een i en j moet bestaan waarvoor w_i = w_j^R maar als n = 1 klopt dit toch niet? Ook in de oplossing wordt dit niet afgedwogen ofwel?

[KommuSoft]

Als n=1, dan kan je voor i en j slechts één waarde kiezen: i=j=1. Dit betekent dus dat die ene groep een palindroom is.

Dit wordt afgedwongen omdat je de overgangsregel S->P kan gebruiken. P maakt een palindroom, en vervogens laat je P naar epsilon evolueren zodat er geen groepen tussen die groep komt te staan.

Voorbeeld:

S -> APB -> PB -> P -> 0P0 -> 01P10 -> 0110

Wat wel ontbrak is dat P ook naar een 0 of 1 moet kunnen afleiden, dit is nu opgelost.

[warreee]

Ah inderdaad, er staat niet dat i en j verschillend moeten zijn :) Bedankt!