Page 7 - 4761

1 ФОРМАЛЬНІ МОВИ І ГРАМАТИКИ

1.1 Ланцюги символів. Операції над ними

Ланцюгом символів (або рядком) називають довільну послідовність символів
записаних один за другим. Поняття символ є базовим в теорії формальних мов і не
потребує визначення.
Надалі ланцюги символів будемо позначати грецькими буквами:  , , . Для
ланцюга символів важливий склад і кількість символів в ньому, а також порядок. Ланцюги
символів  і  рівні    , якщо вони мають один і той же склад символів, однакову
кількість і порядок слідування.
Кількість символів – називається довжиною ланцюга  .Очевидно, якщо    , то

   .
Основною операцією над ланцюгами символів є операція конкатенації
(об’єднання).
Є ще 2-і операції:
R
- обернення ланцюга – запис символів в зворотному порядку (позначається  )
n
- ітерація – повторення ланцюга n раз, де  Nn , n 0 (позначається  )
Серед всіх ланцюгів є важливим – пустий ланцюг. Це ланцюг, який не містить ні
одного символу. Позначається  (деколи е або  ).
Для нього справедливі рівності:
1)   0 ;
2)  :      ;
R
3)   ;
n
4)n  : 0   ; 
0
5)  :    .

1.2 Поняття мови. Формальне визначення

У загальному випадку мова – це заданий набір символів і правил, які встановлюють
способи комбінації цих символів між собою для запису змістовних текстів.
Появі поняттю «формальна мова» передує пошук адекватної математичної моделі
для природних мов (укр., рос. і т. д.). В 1959-60х рр. з’явилось кілька робіт, що заклали
основи формальних мов і формальних граматик. Значний прогрес у цьому напрямку
почався в 1960р., коли було виявлено, що клас формальних мов типу АЛГОЛ-60
збігається з класом контекстно-вільних мов.
Для того, щоб задати штучну мову (мову програмування), необхідно задати
алфавіт, тобто множину символів, кожен з яких можна розмножувати необмеженою
кількістю екземплярів: (позначається V).
Ланцюг  є ланцюгом над алфавітом V: (  V ), якщо в нього входять тільки
символи, що належать множині V. о любого алфавіту може входити  , а може не
входити.
Якщо V деякий алфавіт, то:
+
 V - множина всіх ланцюгів без  ;
*
 V - множина всіх ланцюгів з 
Справедливо:

*
V  V     .

5