Елементи теорії формальних мов. (Тема 2) презентация

Тема 2. Елементи теорії формальних мов 1. Означення формальних мов. Ланцюжки 1.1 Приклади мов 1.2 Задача належності. Способи визначення мов 1.3. Регулярні операції над мовами 2.Метамова БНФ 3. Розширені БНФ 4. Граматики Хомського. Основні поняття. 5. Класифікація граматик Хомського. Приклади. 6. Розпізнавачі

1. Означення формальних мов. Ланцюжки Позначимо – множину всіх слів, крім е (). Припустимо, що ми маємо слово , тоді послідовність , а .

1.1. Приклади формальних мов

1.2. Задача належності. Способи визначення мов

1.3. Регулярні операції над мовами

2. Метамова БНФ

3. Розширені БНФ

Ітераційні дужки “{“ , “}”

4. Граматики Хомського. Основні поняття

G = (N, T, P, S)

Приклади граматик Хомського

Визначимо ряд понять:

Введемо позначення:

5. Класифікація граматик Хомського. Приклади

Адреса://fpm.chnu Гіперпосилання “Системне програмування”, Вкладинка “Програмний супровід”

5. Розпізнавачі Розпізнавач складається з трьох частин: вхідна стрічка;  керуючий пристрій із скінченню пам’яттю; робоча (допоміжна) пам’ять.