Формальна мова

Форма́льна мо́ва — множина скінчених послідовностей символів, які описуються правилами певного виду, які називаються граматикою, або синтаксисом мови (див. формальна граматика).

Синтаксичний поділ у рамках формальної системи. Рядки символів можна поділити на беззмістовні і правильно побудовані формули. Множина таких формул своєю чергою поділяється на теореми і не-теореми.

В тому випадку, коли кожному слову формальної мови співставляється його семантика (сенс, значення, інтерпретація), формальну мову називають інтерпретованою.

Формальні мови можна класифікувати за характером формального апарату, що застосовується для їхнього описання:

Автоматна мова,
Безконтекстна мова,
Категоріальна мова,
Мова породжувана граматиками залежностей, і так далі, або за застосуванням:
Алгоритмічна мова,
Інформаційна мова,
Логіко-математична мова,
Математичні моделі мови.

Більшість формальних мов, створюваних для практичних цілей, є інтерпретованими мовами. Важливий клас інтерпретованих мов становлять мови програмування, а також алгоритмічні мови.

Як математична дисципліна

Формальні мови — математична дисципліна, що вивчає формальні мови, їх задання (граматики), класифікацію, та аналіз.

Дисципліна часто вивчається паралельно з теорією автоматів, або в її складі, оскільки вони є основним інструментом для роботи з мовами (як при генерації, так і при розпізнаванні), та саме вони використовуються на практиці (в програмуванні).

Мета і завдання дисципліни

Формальні мови — це теоретичне підґрунтя до системного програмування, а саме до побудови трансляторів.

Дисципліна займається[1]:

побудова граматики заданого типу, що породжує задану мову, та навпаки (визначення того, яку мову задає граматика)
побудова та мінімізація скінченних автоматів що розпізнають дану (регулярну) мову, та навпаки
побудова регулярних виразів, для даної мови, та навпаки.
аналіз типу формальних мов за ієрархією Чомскі
побудова магазинних (стекових) автоматів для аналізу контекстно-вільних мов, та навпаки.
аналіз мереж Петрі.

Зміст дисципліни

Поняття формальної мови та формальної граматики. Ієрархія Чомскі.
Мови типу 0 і машини Тюрінга.
Регулярні мови і скінченні автомати.
Контекстно-вільні мови і магазинні (стекові) автомати.
Контекстно-залежні мови і лінійно-обмежені машини Тюрінга.
Мережі Петрі.

Джерела

Енциклопедія кібернетики, Ющенко К. Л., т. 2, ст. 618.
Формалізована мова // Філософський енциклопедичний словник / В. І. Шинкарук (гол. редкол.) та ін. — Київ : Інститут філософії імені Григорія Сковороди НАН України : Абрис, 2002. — С. 687. — 742 с. — 1000 екз. — ББК 87я2. — ISBN 966-531-128-X.

Примітки

Теорія автоматів і формальних мов^{[недоступне посилання з липня 2019]} на кафедрі математичних методів та системного аналізу Київського політехнічного інституту.

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Теорія автоматів і формальних мов^{[недоступне посилання з липня 2019]} на кафедрі математичних методів та системного аналізу Київського політехнічного інституту.