Ўзбекистон республикаси алоқА, ахборотлаштириш ва телекоммуникация технологиялари давлат қЎмитаси тошкент ахборот технологиялари университети

4.Белгилар занжири ва улар устидаги амаллар.
Белгилар занжири – бу бири биридан кейин ёзилган белгиларнинг ихтиёрий кетма-кетлигидир.
Белгилар занжири (БЗ) учун таркиб, белгилар сони ва тартиб мухимдир. БЗ α ва β тенг α=β ёки мос тушадилар, агар улар битта белгилар таркибига эга булсалар, бир хил белгилар сонига ва белгиларнинг занжир буйлаб бир хил келиш тартибига эга булсалар. Занжирдаги белгилар сони занжир узунлиги дейилади.
БЗ куйидаги хусусиятларга эгадирлар:
1)Конкатенация – 2 та занжирни йигиндиси ёки купайтмаси αβ
α=“BA”
β=“CL” => αβ=“BACL”
Конкатенация амали коммутиция хусусиятига эга эмас, яъни αβ≠βα. Ассоциативлик хусусиятига эгадир (αβ)γ=α(βγ)
2)Занжирга мурожат – занжир белгиларини тескари тартибда ёзиш α^R, α=“ВАСЯ” => α^R=“ЯСАВ” Ушбу амал учун (αβ)^R=α^Rβ^R хакикат
3)якинлашув – занжирни n марта такрорлаш
4)белгиларнинг буш занжири – бу битта хам белгига эга булмаган занжирдир, λ -буш занжир учун куйидаги хакикат: 1) |λ|=0; 2) ихтиёрий α: λα=αλ=α; 3)λ^R=λ; 4) ихтиёрий n≥0:λⁿ=λ; 5)ихтиёрий α: α⁰=λ
Назорат саволлари

1. 
   Тил синтаксисини нималар аниклайди?
   
2. 
   Тилни синтаксиси ва семантикаси орасида кандай фарк бор?
   
3. 
   Грамматика нима ва у кандай берилади?
   
4. 
   Тилнинг терминал ва нотерминал белгилари кандай фаркланадилар?
   
5. 
   У ёки бу белгининг тилнинг гапларида учрашини кандай изохлайсиз?
   
6. 
   «Бошлангич белги» нима ва у тилнинг бошка белгиларидан нима билан фарк килади?
   
7. 
   Грамматика тугилувчи коидалар оркали берилган булсин.
   

S ->(S) S->E,

S->SS бу ерда S – бошлангич белгиб, Е буш катордир.

Куйидаги каторлар ушбу грамматика буйича генерация килинган тилга тегишлими? Жавобингизни исботланг.

а) катор((1)()), в) катор (()()())