ustify"> і:,.
Нехай,, - регулярні вирази. Тоді властивості регулярних виразів можна записати у вигляді таких висловлювань:
;
;
;
;
;
-;
-;
-;
-;
-;
-;
-;
-;
-.
Всі ці властивості доводяться із застосуванням апарату теорії множин, тому регулярні вирази - це позначення для відповідних множин.
4.9 Способи завдання регулярних мов
Регулярні граматики, кінцеві автомати і регулярні безлічі (і позначають їх регулярні вирази) являють собою три різні способи завдання регулярних мов. Мова є регулярним безліччю тоді і тільки тоді, коли він заданий леволінейной (праволінейной) граматикою. Мова може бути заданий леволінейной (праволінейной) граматикою тоді і тільки тоді, коли він є регулярним безліччю. Мова є регулярним безліччю тоді і тільки тоді, коли він заданий за допомогою кінцевого автомата. Мова розпізнається за допомогою кінцевого автомата тоді і тільки тоді, коли він є регулярним безліччю.
Всі ці три способи еквівалентні. Існують алгоритми, що дозволяють для мови, заданого одним із зазначених способів, побудувати інший спосіб, що визначає той же самий мову.
Наприклад, для знаходження регулярного виразу для мови, заданого праволінейной граматикою, необхідно побудувати і вирішити систему рівнянь з регулярними коефіцієнтами.
У теорії мов програмування найбільш важливу роль відіграє еквівалентність кінцевого автомату і регулярних граматик, оскільки такі граматики використовуються для визначення лексичних конструкцій мов програмування. Створивши на основі відомої граматики автомат, отримуємо распознаватель для даної мови. Таким чином, вдається вирішити завдання розбору для лексичних конструкцій мови.
Для побудови кінцевого автомата на основі відомої регулярної граматики її необхідно привести до автоматного увазі. Безліч станів автомата буде відповідати безлічі нетермінальних символів граматики.
4.10 Властивості регулярних мов
Безліч називається замкнутим щодо деякої операції, якщо в результаті виконання цієї операції над будь-якими його елементами виходить новий елемент, що належить цьому ж безлічі.
Регулярні безлічі замкнуті щодо операцій перетину, об'єднання, доповнення, ітерації, конкатенації, зміни імен символів і підстановки ланцюжків замість символів.
Для регулярних мов розв'язні багато проблем, нерозв'язні для других типів мов. Наприклад, наступні проблеми є розв'язуваними незалежно від того, яким із способів заданий мова: Проблема еквівалентності: Дано два регулярних мови і. Необхідно встановити, чи є вони еквівалентними. Проблема приналежності ланцюжка мови. Дан регулярний мову, ланцюжок символів. Потрібно перевірити, чи належить цей ланцюжок мови. Проблема порожнечі мови. Дан регулярний мову. Необхідно перевірити, чи є ця мова порожнім, тобто знайти хоча б один ланцюжок,.
Іноді буває необхідно довести, є, чи є деякий мову регулярним. Якщо можливо задати це мову однією з розглянутих способів, то він є регулярним. Але якщо такий спосіб знайти не вдається, невідомо, чи то мова не є регулярним, чи то просто не вдалося знайти спосіб його завдання. Існує простий метод перевірки, чи є розглянутий мову регулярним. Доведено, що якщо для деякої мови виконується т.зв. лема про розростанні, то він є регулярним. Якщо ж ця лема не виконується - язик не регулярний.
Лемма про розростанні формулюється таким чином. Якщо дано регулярний мову і досить довгий ланцюжок символів, що належить цій мові, то в ній можна знайти непорожню подцепочку, яку можна повторити як завгодно багато разів, і всі отримані таким чином ланцюжка також належатимуть розглянутого регулярному мови.
Формально лема записується так. Якщо дано мову, то константа, така, що якщо і, то ланцюжок можна записати у вигляді
де, і тоді," .
Приклад. Розглянемо мову
Доведемо, що він не є регулярним, використовуючи для цього лемму про розростанні мов.
Нехай ця мова регулярний, тоді для нього повинна виконуватися лема про розростанні. Візьмемо деяку ланцюжок цієї мови і запишемо її у вигляді. Якщо або, то тоді ланцюжок не належить мові для кожного, що суперечить умовам леми. Якщо ж, то ланцюжок також не належи...
