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

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

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

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

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

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

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

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

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

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

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

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

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

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

Джерела

Примітки

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

Див. також

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