Форма́льна мо́ва — множина скінчених послідовностей символів, які описуються правилами певного виду, які називаються граматикою, або синтаксисом мови (див. формальна граматика).
В тому випадку, коли кожному слову формальної мови співставляється його семантика (сенс, значення, інтерпретація), формальну мову називають інтерпретованою.
Формальні мови можна класифікувати за характером формального апарату, що застосовується для їхнього описання:
- Автоматна мова,
- Безконтекстна мова,
- Категоріальна мова,
- Мова породжувана граматиками залежностей, і так далі, або за застосуванням:
- Алгоритмічна мова,
- Інформаційна мова,
- Логіко-математична мова,
- Математичні моделі мови.
Більшість формальних мов, створюваних для практичних цілей, є інтерпретованими мовами. Важливий клас інтерпретованих мов становлять мови програмування, а також алгоритмічні мови.
Як математична дисципліна
Формальні мови — математична дисципліна, що вивчає формальні мови, їх задання (граматики), класифікацію, та аналіз.
Дисципліна часто вивчається паралельно з теорією автоматів, або в її складі, оскільки вони є основним інструментом для роботи з мовами (як при генерації, так і при розпізнаванні), та саме вони використовуються на практиці (в програмуванні).
Мета і завдання дисципліни
Формальні мови — це теоретичне підґрунтя до системного програмування, а саме до побудови трансляторів.
Дисципліна займається:
- побудова граматики заданого типу, що породжує задану мову, та навпаки (визначення того, яку мову задає граматика)
- побудова та мінімізація скінченних автоматів що розпізнають дану (регулярну) мову, та навпаки
- побудова регулярних виразів, для даної мови, та навпаки.
- аналіз типу формальних мов за ієрархією Чомскі
- побудова магазинних (стекових) автоматів для аналізу контекстно-вільних мов, та навпаки.
- аналіз мереж Петрі.
Зміст дисципліни
- Поняття формальної мови та формальної граматики. Ієрархія Чомскі.
- Мови типу 0 і машини Тюрінга.
- Регулярні мови і скінченні автомати.
- Контекстно-вільні мови і магазинні (стекові) автомати.
- Контекстно-залежні мови і лінійно-обмежені машини Тюрінга.
- Мережі Петрі.
Див. також
Примітки
- Теорія автоматів і формальних мов[недоступне посилання з липня 2019] на кафедрі математичних методів та системного аналізу Київського політехнічного інституту.
Джерела
- Енциклопедія кібернетики, Ющенко К. Л., т. 2, ст. 618.
- Формалізована мова // Філософський енциклопедичний словник / В. І. Шинкарук (гол. редкол.) та ін. — Київ : Інститут філософії імені Григорія Сковороди НАН України : Абрис, 2002. — С. 687. — 742 с. — 1000 екз. — ББК 87я2. — ISBN 966-531-128-X.
| Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |