На головну

Операції об'єднання і перетину регулярних мов

Теорема. Доповнення, об'єднання і перетину

регулярних мов знову є регулярними мовами



25. Недетермінірованние автомати і розпізнаються ними мови.




? 24.1 Регулярність конкатенації і L *.

Недетермінірованний автомат для L *


26. Регулярні вирази.

Для позначення регулярних мов зручно використовувати регулярні вирази. Кожен регулярний мову можна записати у вигляді рядка, що містить символи алфавіту, символ ?, круглі та фігурні дужки, і символи * і ?.

На приклад, L = (({0} ? {1}) *) * ? ({0} {1}) - регулярна мова, що належить класу R4. Регулярним виразом для заданого регулярного мови називається рядок, отримана видаленням фігурних дужок у записі цієї мови. Так регулярним виразом для розглянутого вище мови L буде рядок ((0?1) *) * ? (01). Для кожної мови існує нескінченно багато регулярних виразів. Наприклад, рядок ? ? ((0 ? 1) *) * ? (01) є регулярним виразом для того ж мови L. Наведемо більш суворе визначення регулярних виразів по індукції.

Визначення. Регулярні вирази в алфавіті ? і регулярні мови,

для позначення яких вони служать, визначаються наступним чином:

1. ? - регулярний вираз, що означає порожній мову,

2. якщо x ? ?, то x - регулярний вираз, що означає мову {x},

3. якщо p і q - регулярні вирази, що позначають мови P і Q відповідно, то

- (Pq) - регулярний вираз, що означає мову P Q,

- (P ? q) - регулярний вираз, що означає мову P ? Q,

- (P) * - регулярний вираз, що означає мову P *,

4. інших регулярних виразів в мові ? немає.

Подібно арифметичним виразам, в регулярних виразах можна опускати дужки, призначивши пріоритет кожної операції. Прийнято вважати, що найвищий пріоритет у зірочки Кліні, нижчий у конкатенації, і найнижчий у об'єднання. Так опускаючи дужки в регулярному виразі ((0?1) *) * ? (01), отримаємо рядок (0 ? 1) ** ? 01.

Теорема Кліні. Мова над алфавітом X є регулярною тоді і тільки тоді, коли він може бути виражений через мови ?, {?}, {a}, де a ? X, і операції ?, · і *.

27. Машини Тьюринга. Обчислюваних мови. Теза Черча-Тьюринга. Вичіслімость регулярних мов.

Машина Тьюринга визначається кортежем виду

де  - Кінцеве безліч станів;  - Кінцевий вхідний алфавіт;  - Символ, званий маркером початку стрічки;  - Символ, званий порожнім (або пропуском);  - Символи, звані символами напрямки руху головки;  - початковий стан;  - Заключне стан;  - Функція переходів, що є відображенням виду причому значення  , Якщо воно визначено, є кінцеве (можливо, і пусте) безліч впорядкованих трійок з відповідного декартова твори.

Функція переходів може бути записана у вигляді системи команд. Кожна команда є слово виду

де .

слово  (До стрілки) називається лівою частиною команди, а слово  (Після стрілки) - правою частиною команди.

Неформально роботу машини Тьюринга можна представити в такий спосіб. Машина має пристрій управління, яке може перебувати в одному з станів безлічі  , Напівнескінченної стрічку, розділену на осередки, в кожній з яких може бути записаний символ з алфавіту  , Причому крайня ліва комірка зберігає символ  , І головку читання-запису, яка в кожен момент дискретного часу оглядає якусь одну клітинку стрічки. символ  (Пропуск) не слід плутати з порожньою ланцюжком - це спеціальний символ, що означає порожню, тобто НЕ зберігає символів алфавіту  , Осередок стрічки. Команда, записана вище, дозволяє машині Тьюринга, пристрій управління якої знаходиться в стані  , А головка оглядає осередок, що зберігає символ  , Перевести пристрій управління в стан  , Записавши в оглядається осередок символ  (Який може і збігатися з  ), І залишити головку на колишньому місці, якщо  , Зрушити її на одну клітинку вліво, якщо  , Або на одну клітинку вправо, якщо .

Будемо говорити, що машина Тьюринга  застосовна до слова  , Якщо з конфігурації  виводиться конфігурація  для деякого .

слово  будемо називати в цьому випадку результатом застосування машини Тьюринга  до речі  і позначати його  . Факт застосування машини  до речі  будемо позначати  ; якщо ж  не може бути застосована до  , То будемо записувати .

Безліч всіх слів  , Таких, що  , Називається областю застосовності машини Тьюринга .

словникова функція  в алфавіті  називається обчислюваною по Тьюрингу, якщо існує така машина Тьюринга  з вхідним алфавітом  , що містить  , що

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


28. Зміни і обчислення машин Тьюринга. Універсальна обчислювана функція. Теорема Кліні про нормальній формі.

Конфігурація машини Тьюринга  є кортеж

з конфігурації  безпосередньо виводиться конфігурація  , якщо .

з конфігурації  безпосередньо виводиться конфігурація  , якщо .

з конфігурації  безпосередньо виводиться конфігурація  , якщо .

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

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

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



 алгоритм |  Теорема Кліні.

 Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Вершин, ребер і компонент зв'язності. |  Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху. |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера. |  Доведення формули Ейлера для плоских зв'язкових графів |  доведення коректності |

© um.co.ua - учбові матеріали та реферати