2014 2015 2016 2017 2018

Raidžių žaidimas

Taškai: 6

Bebras Bronius žaidžia raidžių sekų žaidimą. Jis yra sukūręs keletą taisyklių, kaip sudaryti naujas raidžių sekas:
    1. Kiekviena seka pradedama raide S.
    2. Tinkamą seką sudaro tik raidės A ir (arba) B.
    (sudarant seką gali būti pasitelkiamos raidės S ir X.)
    3. Raidė S gali būti keičiama į AX.
    4. Raidė X gali būti keičiama į AXB.
    5. Raidė X gali būti keičiama į B.
Pavyzdžiui, raidžių seka AABB gali būti gaunama šiuo būdu:
S (1 taisyklė) → AX (3 taisyklė) → AAXB (4 taisyklė) → AABB (5 taisyklė).
Kuri iš raidžių sekų sudaryta pagal šio žaidimo taisykles?

A) AX
B) A
C) AAAABBBB
D) AABBAABB

Paaiškinimas

Pateiktomis taisyklėmis kuriama laisvojo konteksto kalba (angl. context free language). Šią kalbą atitinka tokia gramatikos taisyklių aibė:
1. S→AX
2. X→AXB
3. X→B
Laisvojo konteksto kalbos generavimą galima nusakyti taip: paimamas vienintelis simbolis S, pasirenakama taisyklė, pagal kurią kairėje sekos pusėje yra S. Šis simbolis keičiamas eilute, esančia ženklo „→“ dešinėje. Veiksmai kartojami, kol eilutėje nelieka simbolių, pagal taisyklę esančių ženklo „→“ kairėje.
Ženklo „→“ kairėje esantys simboliai vadinami neterminaliniais, o ženklo „→“ dešinėje – terminaliniais simboliais.
Neterminaliniai simboliai žymi baigtinio automato būsenas. Baigtinis automatas veikia kaip kalbos atpažinimo įtaisas.
Galima sukurti nedeterministinį automatą, kuriuo nustatoma, ar seka yra žodis.

Atsakymas

A) Seka neteisinga, nes pagal 2 taisyklę seką gali sudaryti tik raidės A ir (arba) B.
B) Seka neteisinga, nes trumpiausią seką sudaro dvi raidės: S→AX→AB (kiekviena taisyklė seką daro ilgesnę už ankstesnę).
C) AAAABBBB yra teisinga seka (S→AX→AAXb→AABB).
D) Seka neteisinga, nes nėra taisyklės, pagal kurią raidę A būtų galima užrašyti dešinėje AB.