In 1982 vond de 74-jarige David Martin restanten van een postduif in de schoorsteen van zijn huis in Bletchingley (Surrey, Engeland).

Aan de poot van de duif was een gecodeerd bericht bevestigd dat vermoedelijk vanuit Frankrijk verzonden was op D-Day (6 juni 1944):

AOAKN HVPKD FNFJW YIDDC
RQXSR DJHFP GOVFN MIAPX
PABUZ WYYNP CMPNW HJRZH
NLXKG MEMKK ONOIB AKEEQ
WAOTA RBQRH DJOFM TPZEH
LKXGH RGGHT JRZCQ FNKTQ
KLDTS FQIRW AOAKN 27 1525/6

Maar wat betekent het? Niemand die het weet — het bericht is nog steeds niet ontcijferd. In november 2012 deed het Government Communications Headquarters¹ (GCHQ) — de Britse inlichtingendienst die zich bezighoudt met informatiebeveiliging  — hierover de volgende aankondiging:

Alhoewel het teleurstellend is dat we nog altijd niet kunnen lezen wat er in het bericht staat dat deze dappere postduif terugbracht, is het wel een eerbetoon aan de vaardigheden van de codemakers uit oorlogstijden dat ze ondanks de enorme druk waaronder ze moesten werken, toch een code konden bedenken die zowel toen als nu niet te ontcijferen was.

Opgave

Elke regel van het tekstbestand pigeon.txt² is een patroon $$p \in \mathcal{P}$$. De verzameling $$\mathcal{P}$$ bestaat uit alle mogelijke groepen van twee of meer hoofdletters die telkens door één spatie van elkaar gescheiden zijn. Gevraagd wordt:

1. Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,$$vier opeenvolgende groepen van $$p$$ bevatten respectievelijk de letters G, C, H en Q$$\,\}$$

     voorbeeld:	XHASSE QPXKTN NRXGCM QAZGCE FCCOSS LKAXOH BOHQKE GGFPZS $$\in \mathcal{P}_1$$
     	OGKQS KMGJA PJJYN EABNC CKNKT IXLRU VLOTM BWWRS $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,p\ $$bevat een groep waarin klinkers$$\ ^{(*)}$$ en medeklinkers elkaar afwisselen$$\,\}$$

     (*) de klinkers zijn A, E, I, O en U
     

     voorbeeld:	UDACBG UYAZAM DJSUBU WJKMBC NTCGCH DIDEVO RHWDAS $$\in \mathcal{P}_2$$
     	GWGJK KPJAN VDMMO UERFB XRDWB ZHKEI XRZIE IYOZR $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$de tweede letter van elke groep$$\ ^{(*)}$$ van $$p$$ verschilt van de eerste letter van de vorige groep$$\,\}$$

     (*) behalve van de eerste groep, die geen voorgaande groep heeft
     

     voorbeeld:	VIBGHD QRTDSE ATHDQD YGOTUU JFHAMC OKBKJE WQJIZS $$\in \mathcal{P}_3$$
     	ILOJBS AHJBRE QSSXYE DQOQKS DEXKGA OITOWW KDQJGS $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,$$alle groepen van $$p$$ hebben een letter die minstens twee keer in de groep voorkomt$$\,\}$$

     voorbeeld:	ATGSGB RDMNDE ZRVLZC AJANXA QNVHVM NMYMHE $$\in \mathcal{P}_4$$
     	NFLRPM KTXHPI LOEXTL PZXJSD OGQXBL OPWPWY $$\not \in \mathcal{P}_4$$

   Geef telkens een Unix commando waarin de reguliere expressie gebruikt wordt door een commando uit de grep familie om enkel de regels van het tekstbestand naar stdout te schrijven waarvan het patroon $$p$$ behoort tot $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$.

2. Bepaal als volgt de woorden $$w_1\ w_2\ w_3\ w_4$$ van een geheime boodschap:

   • het woord $$w_1$$ krijg je door de laatste letters samen te voegen van alle groepen op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P}_2$$

   • het woord $$w_2$$ krijg je door de laatste letters samen te voegen van alle groepen op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P}_3$$

   • het woord $$w_3$$ krijg je door de laatste letters samen te voegen van alle groepen op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P}_4$$

   • het woord $$w_4$$ krijg je door de laatste letters samen te voegen van alle groepen op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_4 \cap \mathcal{P}_1$$

   Geef telkens een Unix commando waarin de reguliere expressies voor de verzamelingen $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$ gebruikt worden door commando's uit de grep familie om het woord $$w_j\ (j = 1, 2, 3, 4)$$ op te zoeken in het tekstbestand en uit te schrijven naar stdout. Hierbij is het niet toegelaten om het woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).