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.

 

 
Informacija atnaujinta 2016-10-18 10:55:36
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.