Кінцеві автомати та регулярні мови, дискретна математика

У цьому розділі ми починаємо виклад елементів теорії формальних мов.

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

Вивчаючи мови, слід мати на увазі три основних аспекти.

Перший з них - синтаксис мови. Мова - це якийсь безліч "слів", де "слово" є певна кінцева послідовність "букв" - символів якогось заздалегідь фіксованого алфавіту. Терміни "буква" і "слово" можуть розумітися по-різному (математичне визначення цих термінів буде дано нижче). Так, "буквами" можуть бути дійсно літери алфавіту якогось природного або формальної мови, наприклад української мови або мови програмування "Паскаль". Тоді "словами" будуть кінцеві послідовності "букв": крокодил "," integer ". Такі слова називають" лексемами ". Але" буквою "може бути" слово "(" лексема ") в цілому. Тоді" слова "- це пропозиції природного мови або програми мови програмування. Якщо фіксоване якесь безліч "букв", то не кожна їх послідовність буде "словом", тобто Елексемой "даного мови, а тільки така послідовність, яка підпорядковується певним правилам. Слово "крикаділ" не є лексемою української мови, а слово "iff" не є лексемою в "Паскалі". Пропозиція "Я люблю ти" не є правильним пропозицією української мови, точно так же, як і запис "х: = = t" не є правильно написаний оператор присвоювання "Паскаля". Синтаксис * мови і являє собою систему правил, відповідно до яких можна будувати "правильні" послідовності "букв". Кожне слово мови характеризується певною структурою, специфічною саме для даної мови. Тог да необхідно, з одного боку, розробити механізми перерахування, або породження, слів із заданою структурою, а з іншого - механізми перевірки того, що дане слово належить даному мови. Перш за все саме: ці механізми і вивчає класична теорія формальних мов.

Другий аспект - семантика мови. Семантика ** передбачає зіставлення словами мови якогось "сенсу", Езначенія ". Наприклад, записуючи математичну формулу, ми повинні дотримуватися певних синтаксичні правила (розстановка дужок, правопис символів, порядок символів і т.п.), але, крім цього, формула має цілком певний сенс, щось означає.

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

* Слово "синтаксис" походить від давньогрецьких "syn" - "разом" і "taxis" - "порядок, лад". Таким чином, синтаксис можна розуміти як "складання".

** Від давньогрецьких слів "sema" - "знак, знамення" і "semanticos" - "позначає".

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

Алфавіт, слово, мова

Розглянемо найпростіше поняття теорії мов - поняття алфавіта.Подробнее

породжують граматики

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