Формальна мова
Форма́льна мо́ва — множина скінчених послідовностей символів, які описуються правилами певного виду, які називаються граматикою, або синтаксисом мови (див. формальна граматика).
В тому випадку, коли кожному слову формальної мови співставляється його семантика (сенс, значення, інтерпретація), формальну мову називають інтерпретованою.
Формальні мови можна класифікувати за характером формального апарату, що застосовується для їхнього описання:
і так далі, або за застосуванням:
Більшість формальних мов, створюваних для практичних цілей, є інтерпретованими мовами. Важливий клас інтерпретованих мов становлять мови програмування, а також алгоритмічні мови.
Зміст |
Як математична дисципліна[ред.]
Формальні мови — математична дисципліна, що вивчає формальні мови, їх задання (граматики), класифікацію, та аналіз.
Дисципліна часто вивчається паралельно з теорією автоматів, або в її складі, так як вони є основним інструментом для роботи з мовами (як при генерація, так і при розпізнавання), та саме вони використовуються на практиці (в програмуванні).
Мета і завдання дисципліни[ред.]
Формальні мови - це теоретичне підґрунтя до системного програмування, а саме до побудови трансляторів.
Дисципліна займається[1]:
- побудова граматики заданого типу, що породжує задану мову, та навпаки (визначення того, яку мову задає граматика)
- побудова та мінімізація скінченних автоматів що розпізнають дану (регулярну) мову, та навпаки
- побудова регулярних виразів, для даної мови, та навпаки.
- аналіз типу формальних мов за ієрархією Хомського
- побудова магазинних (стекових) автоматів для аналізу контекстно-вільних мов, та навпаки.
- аналіз мереж Петрі.
Зміст дисципліни[ред.]
- Поняття формальної мови та формальної граматики. Ієрархія Хомського.
- Мови типу 0 і машини Тюрінга.
- Регулярні мови і скінченні автомати.
- Контекстно-вільні мови і магазинні (стекові) автомати.
- Контекстно-залежні мови і лінійно-обмежені машини Тюрінга.
- Мережі Петрі.
Джерела інформації[ред.]
- Енциклопедія кібернетики, Ющенко К. Л., т. 2, ст. 618.
- ↑ Теорія автоматів і формальних мов на кафедрі математичних методів та системного аналізу Київського політехнічного інституту.
