Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



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

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

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


Визначення

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

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

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


Операції

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

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

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


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Формальна верифікація
Формальна система
Формальна семантика
Формальна логіка
Формальна граматика
Формальна верифікація
Формальна система
Мова
На'ві (мова)
© Усі права захищені
написати до нас