In 1605 ontwikkelde de Britse filosoof, wetenschapper en politicus Francis Bacon een versleutelingsmethode die in twee stappen werkt.

Bij het coderen wordt elke letter van het originele bericht eerst vertaald naar een groep van vijf letters uit een tweeletter-alfabet (bijvoorbeeld a en b). In bovenstaande figuur zie je bijvoorbeeld de sleutel met het tweeletter-alfabet (a en b) die Francis Bacon gebruikte in zijn werk De Augmentis Scientiarum¹ (1605). Omdat het ging om een werk in het Latijn, was het toenertijd gebruikelijk om de letters i en j aan elkaar gelijk te stellen, net zoals de letters u en v. Aangezien het gaat om een binaire codering die gebruik maakt van twee symbolen op vijf posities, kunnen er dus in totaal $$2^5 = 32$$ symbolen gecodeerd worden. Het is dus perfect mogelijk om de Baconversleuteling toe te passen met een sleutel die elk van de 26 letters uit ons alfabet op een unieke manier codeert, en bovendien nog ruimte laat voor 6 extra karakters (bijvoorbeeld een spatie en enkele leestekens).

In tweede instantie wordt een willekeurige tekst genomen of verzonnen, die wordt uitgeschreven aan de hand van twee verschillende lettertypes. Het ene lettertype komt overeen met de letter a, en het andere lettertype met de letter b uit de vorige stap. Hierbij maakt het dus niet uit welke letter gebruikt wordt, enkel het lettertype wordt gebruikt voor de code. In bovenstaande figuur zie je de lettertypes die Francis Bacon gebruikte. Om te verhullen dat het om een gecodeerd bericht ging, maakte hij gebruik van twee lettertypes die vaak slechts op een subtiele manier van elkaar verschillen.

In plaats van te spelen met lettertypes, zou je bijvoorbeeld ook de letter a kunnen voorstellen door kleine letters, en de letter b door hoofdletters. Laat ons dat eens toepassen in een voorbeeld waarin we het woord ALICE willen versleutelen. In eerste instantie vervangen we elke letter door een reeks van vijf a's of b's:

  A     L     I     C     E
aaaaa ababa abaaa aaaba aabaa

Daarna coderen we deze boodschap in de tekst Draco Dormiens Numquam Titillandus:

aaaaa ababa abaaa aaaba aabaa
draco dOrMI eNsnu mquAm tiTil

Om het principe nog duidelijker te illustreren hebben we hierbij alle hoofdletters en de corresponderende letters b in het vet weergegeven. In een handschrift valt een codering met twee nagenoeg gelijke lettertypes haast niet op.

Opgave

Het tekstbestand bacon.txt² bevat de baconversleuteling van een reeks woorden (die enkel bestaan uit kleine letters). Elke regel van het bestand bevat de baconversleuteling van een woord, een spatie en het originele woord dat versleuteld werd. De baconversleuteling maakt gebruik van hoofdletters en kleine letters om respectievelijk de letters b en a uit de versleuteling voor te stellen.

In de rest van deze opgave gebruiken we de term letter als we expliciet geen onderscheid willen maken tussen hoofdletters en kleine letters. Gevraagd wordt:

1. Bepaal reguliere expressies voor elk van onderstaande verzamelingen. Daarbij staat $$\mathcal{B}$$ voor de verzameling van alle mogelijke baconversleutelingen van woorden, of met andere woorden voor alle reeksen van letters waarvan de lengte een veelvoud is van vijf.

   • $$\alpha = \{b \in \mathcal{B}\,|\,$$ als je alle letters uit $$b$$ weglaat die geen A, B, C, O of N zijn, dan spel je de letters van het woord BACON$$\,\}$$

     voorbeelden:	phuBUwYhdzHxgJmSatMPsUEIvWmzjGIqlCEKonHl distorts $$\in \alpha$$
     	uzsIghksxnKeqNCJcaDDgBtekmMBxXxeDIk catting $$\not\in \alpha$$

   • $$\beta = \{b \in \mathcal{B}\,|\, b$$ bevat een reeks van minstens vier opeenvolgende hoofdletters die ingesloten zit tussen dezelfde kleine letter$$\,\}$$

     voorbeelden:	GnlCyycqHeTilaZoLyjmvLGqpiWHOQTTinm scrimpy $$\in \beta$$
     	oLRhuiaiabaAllryJZzXGyhQNfnymfvEymgeKAgF maintain $$\not\in \beta$$

   • $$\gamma = \{b \in \mathcal{B}\,|\, b$$ bestaat uit alternerende groepen van twee klinkers en twee medeklinkers $$\,\}$$

     voorbeelden:	FniIfReEpviAZqiuSQiaxxIolYuamFeOhDIoWQEugYAuTxiOQs summerlong $$\in \gamma$$
     	ZveSoxrCuqhjwSuCcsUChLpglyHlQNmPgtgHuuVSfBiitmlTitRsmMh sectilities $$\not\in \gamma$$

   • $$\delta = \{b \in \mathcal{B}\,|\,$$elke letter komt hoogstens drie keer voor in $$b\,\}$$

     voorbeelden:	HsaNWhbCMJvYygvrnyZcdMrKaEwjRbhtFguJfqDO thickset $$\in \delta$$
     	ufbvZglmpkQsrUxuFDIrvDXWFdxEGQhYtddaWcTN basophil $$\not\in \delta$$

   Gebruik een commando uit de grep familie om enkel die regels van het bestand bacon.txt³ te selecteren die behoren tot de opgegeven verzameling.

   Opmerking

   Gebruik voor deze opgave een recente versie van GNU grep. Op helios is een recente versie van GNU grep geïnstalleerd, maar Mac OS X gebruikt standaard typisch een oudere versie van GNU grep. Mac gebruikers kunnen voor de zekerheid dus best hun grep versie updaten naar de meest recente versie.

2. Beschouw de verzamelingen $$\alpha$$, $$\beta$$, $$\gamma$$ en $$\delta$$ zoals hierboven gedefinieerd. Gebruik nu deze verzamelingen om op de volgende manier een boodschap bestaande uit vier woorden te achterhalen:

   • het eerste woord staat op de unieke regel uit de verzameling $$\alpha \cap \beta$$

   • het tweede woord staat op de unieke regel uit de verzameling $$\beta \cap \gamma$$

   • het derde woord staat op de unieke regel uit de verzameling $$\gamma \cap \delta$$

   • het vierde woord staat op de unieke regel uit de verzameling $$\delta \cap \alpha$$

   Geef telkens een Unix commando dat elk van deze woorden opzoekt in het bestand en uitschrijft naar standaard uitvoer (zonder het patroon dat aan het woord voorafgaat). Hierbij is het dus niet toegelaten om het woord letterlijk uit te schrijven (bv. echo xxx).