Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Формална граматика

Алгоритъмът предварително е дефиниран като азбучен оператор с крайна система от правила за преобразуване. За да напишете входни, междинни и изходни думи, използвайте някаква азбука. По някакъв начин трябва да се опишат правилата за преобразуване. Очевидно това изисква някакъв език. Подходящ ли е обичайният говорим език за описанието на алгоритъма?

Всеки естествен език възниква като средство за комуникация между хората. Поради тази причина той има такива функции като:

· Променливост, която се състои в непостоянството на речника на езика;

· Двусмисленост в тълкуването на фрази от различни хора;

· Резервиране, както е описано в глава „Кодиране на символна информация”.

Тези характеристики не позволяват използването на естествен език за писане на алгоритъм, тъй като едно от свойствата на алгоритъма е неговият детерминизъм, т.е. еднозначност на стъпките от всеки изпълнител. Най-простият начин за преодоляване на нежеланите свойства на естествените езици е изграждането на изкуствени езици със строг синтаксис и пълна семантична определеност - тези езици се наричат формални.

На всеки език, естествен или изкуствен, могат да се разграничат два компонента: синтаксис и семантика. Синтаксис (граматика на език) е набор от правила, според които конструкции, допустими на даден език, са изградени. Семантика - семантичната страна на езика - тя свързва единиците и конструкциите на езика с някой външен свят, за да опише кой език се използва.

За да опише официален език, е необходим друг език, с който ще се създават езикови конструкции. Описаният формален език се нарича обектен език, а езикът, с който се прави описанието, е метаезик. Метаязикът трябва да предоставя както описание на структурните единици на езика, така и правилата за комбинирането им в допустими изречения, както и съдържанието (значението) на езиковите конструкции.

Всяка граматика започва с указание на азбуката, т.е. набора от символи, чрез който се изграждат езикови конструкции.

Синтаксисът на официалния език се определя от определена система от правила (генериращата система), която от малък набор от начални структури генерира всички допустими комбинации от тях, т.е. Езикът се формира като съвкупност от комбинации от изходни конструкции, позволени от правила. Освен това, синтаксисът съдържа изявление за условието, което се изпълнява за пълни езикови конструкции и не се изпълнява по друг начин.

В допълнение към синтаксиса се създава система от правила, която позволява на езиковите конструкции да имат смисъл - тези правила формират семантиката на езика.

Формалната граматика е система от правила, която описва набор от крайни поредици от символи на формална азбука.

Крайните вериги от символи се наричат изречения на формален език, а самата верига е езикът, описан в тази граматика.

Наборът от синтактични правила на официалния език е подобен на пермутационната система, използвана в нормалните марковски алгоритми. Заключението в тази генеративна граматика е последователност от вериги, в която всяко, започвайки от второто, се получава от предишното приложение на всяко правило за извод.

Формалната граматика е дадена от подредена четворка { T , N, S, P } , където T и N са несвързани крайни множества, които съставляват азбука или речник на генериран официален език; Т се нарича набор (речник) на крайни символи; N - набор (речник) на не-терминални (спомагателни) знаци. S е началният (отличителен) спомагателен символ от множеството N. Р е набор от правила за извличане на езикови конструкции (замествания) от избрания спомагателен символ, имащ формата gh, където g и h са вериги, състоящи се от терминални и нетерминални символи.

Замените работят както следва: ако низът в трансформираната верига е g , тогава той се заменя с думата h. Единственото ограничение за вида замествания е, че думата g не може да се състои само от крайни символи. Това означава, че получаването на определена стъпка от верига, състояща се само от крайни символи, означава прекратяване на процеса на генериране - тази верига е правилната, пълна конструкция на генерирания език. Заместванията Р могат да бъдат приложени към трансформируемата верига във всякакъв ред.





Вижте също:

Кодиране на числа в компютър и действия върху тях

Пример 7.7

Структурни и функционални модели

Пример А.1

Еквивалентни автомати

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru