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
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.
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.