Мови формальні

У Вікіпедії є статті про інші значення цього терміна: Мова (значення).

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

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

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

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

• ,
• ,
• ,
• , і так далі, або за застосуванням:
• Алгоритмічна мова,
• Інформаційна мова,
• ,
• Математичні моделі мови.

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

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

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

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

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

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

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

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

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

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

Див. також

• Формальні граматики
• Граматика залежностей
• Мова програмування
• Синтаксичний аналіз
• Скінченний автомат
• Висота ітерації мови

Примітки

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

Джерела

Українською

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

Література

• Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.