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

3.Формал тил (ФЯ) ва формал грамматика (ФГ) тушунчаси
Формал тил – бу сузлардан ташкил топган гапларнинг тупламидир (каторлар).
Катор – бу чекланган узунликдаги белгилар кетма-кетлигидир (белгилар бири биридан кейин ёзилган). Ушбу белгиларнинг хар бири аввалдан берилган алфавитнинг булаги хисобланади.
Алфавит – белгиларнинг ёки литераларнинг буш булмаган тугалланган туплами булиб, улар ёрдамида каторларни куриш мумкин. Формал тилда каторлардан гаплар курилади ва бу каторлар белгилар занжири деб аталади.
Изох:
Формал тилни берилиши учун унинг алфавит ива формал граматикасини курсатиш зарур.
Формал грамматика – каторлар тупламини ифодалаш учун керак буладиган коидалар тизимидир (белгиларнинг тугалланган кетма-кетлиги).
Уз навбатида каторлар гапларни ташкил этади ва х.к. Бундай каторлар туплами тилни ташкил этади. Тил кандайдир формал грамматика билан ифодаланади деб хисобласак, грамматика тилни юзага келтиради.
Фараз килайлик алфавит бу ={0, 1} булсин. Ушбу алфавитдан 01001 катор ташкил этилсин. Занжирдаги белгилар сони занжирнинг узунлиги m деб аталади (белгиларнинг мос тушишига богликсиз равишда). Буш занжир деб узунлиги m=0 булган занжир аталади. У .. ёки .. белгиланади.
Белги алфавитда аникланган каторлар тупламини англатади.
..={0,1,01,10,101,110,..}.
Буш туплам ихтиёрий тупламга киради.
L алфавитнинг формал тили .. дебкандайдир ихтиёрий.. . кисмтупламга айтилади. Знак .. разница с .. в одном символе. .. не включает в сея пустую строку.
Хар бир формал тил гаплари кандайдир коидалардан келиб чиккан холда тузилади. Бу коидалар тилнинг синтаксисини ташкил этади. Формал тилнинг муаммоларидан бири тил синтаксисини ифодалашдан иборатдир. Мазмуни: агар тиллар куп булмаган тугалланган гаплардан ташкил топган булганларида эди, у холда уларни санаб чикиш мумкин булар эди ва конструкцияларнинг тугрилиги ущбу тупламга тегишли ёки тегишли эмаслиги билан текширилар эди.
Лекин мумкин булган гаплар сони шунчалик купки, уларни санаб чикишнинг сира иложи йук.
Шунинг учун тиллар синтаксисини ифодаловчи махсус –метатиллар (тиллар устида тиллар) мавжуд. Ушбу тилда тил конструкциясини тугрилигини аникловчи коидалар тизимини ифодаланади.