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

Не слід плутати з формальним стилем мови.

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

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

Визначення

Формальна мова може бути визначений по-різному, наприклад:

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

Якщо алфавіт заданий як {a, b}, а мова L включає в себе всі слова над ним, то слово ababba належить L. Пусте слово (тобто рядок нульової довжини) допускається і часто позначається як e, ε або Λ.

Деякі приклади формальних мов:

безліч всіх слів над {a, b}
безліч {A ^n} , Де n - невід'ємне число, а a ⁿ означає, що a повторюється n раз
безліч синтаксично коректних програм в даному мові програмування

Операції

Деякі операції можуть бути використані для того, щоб породжувати нові мови з даних. Припустимо, що L ₁ і L ₂ є мовами, визначеними над деяким загальним алфавітом.

Конкатенація (зчеплення) L ₁ L ₂ містить всі слова, що задовольняють формі v w , Де v - Це слово з L ₁ , А w - Слово з L ₂ .
Перетин $L_1 \ cap L_2$ містить всі слова, що містяться і в L ₁ , І в L ₂ .
Об'єднання $L_1 \ cup L_2$ містить всі слова, що містяться або в L ₁ , Або в L ₂ .
Доповнення мови L ₁ містить всі слова алфавіту, які не містяться в L ₁ .
Права ставлення L ₁ / L ₂ містить всі слова v , Для яких існує слово w в L ₂ таке, що v w находідось в L ₁ .
Замикання Кліні $L_ {1 }^{*}$ містить всі слова, які можуть бути записані у формі w ₁ w ₂... w _n , Де w _i міститься в L ₁ і $n \ ge 0$ . Слід пам'ятати, що це включає і пусте слово $\ Epsilon$ , Так як n = 0 допустимо за умовою.
Звернення $L_ {1} ^ {R}$ містить звернені слова з L ₁ .
Змішання L ₁ і L ₂ містить всі слова, які можуть бути записані у формі v ₁ w ₁ v ₂ w ₂... v _n w _n , Де $n \ ge 1$ і v ₁,..., v _n є такими словами, що зв'язок v ₁... v _n знаходиться в L ₁ , А w ₁,..., w _n є такими словами, що w ₁... w _n перебувають у L ₂ .

Список літератури

Хопкрофта, Дж., Мотвані, Р., Дж. Ульман. Введення в теорію автоматів, мов і обчислень. М.: Вільямс, 2002 (пер. видання Addison Wesley). ISBN 5-8459-0261-4
Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теорія і реалізація мов програмування / / М.: МЗ-Пресс, 2006 р., 2-е вид. ISBN 94073-094-9.
Обрані книги з курсів "Теорія і реалізація мов програмування" та "Формальні мови трансляцій"